[洛谷P5190][COCI 2010] PROGRAM

题目大意：给你$k(k\leqslant10^6)$个数，$f(x)$表示$x$的约数在$k$个数中出现的次数，在这任何数都是$0$的约数。$m(m\leqslant10^6)$次询问，每次给出$l,r(l,r\leqslant10^6)$，求$\sum\limits_{i=l}^rf(i)$

题解：求出每个数出现次数，直接加到它的倍数上，$O(n\log_2n)$，然后前缀和，直接输出，注意$l=0$的情况

卡点：无

C++ Code：

#include <cstdio>

#define maxn 1000010

int n, k, m;

long long __pre__[maxn], *pre = __pre__ + 1;

int cnt[maxn];

int main() {

	scanf("%d%d", &n, &k);

	for (int i = 0, x; i < k; ++i) {

		scanf("%d", &x);

		++cnt[x];

	}

	for (int i = 1; i < n; ++i) {

		for (int j = 0; j < n; j += i) pre[j] += cnt[i];

	}

	for (int i = 1; i < n; ++i) pre[i] += pre[i - 1];

	scanf("%d", &m);

	while (m --> 0) {

		static int l, r;

		scanf("%d%d", &l, &r);

		printf("%lld\n", pre[r] - pre[l - 1]);

	}

	return 0;

}

巴特西

[洛谷P5190][COCI 2010] PROGRAM

最新文章

热门文章