题目大意：给你$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;
}
原文：https://www.cnblogs.com/Memory-of-winter/p/10356622.html