CodeForces - 385C Bear and Prime Numbers——素数筛法

CodeForces - 385C Bear and Prime Numbers——素数筛法

在筛素数时计算每个数可以对应多少个题目中给定的数ai， 满足这个数是ai的因子， 然后预处理前缀和，O（1）完成查询

#include #include #include #include using namespace std;const int maxn = 1e6;const int maxm = 1e7 + 5;int n, m, a[maxn], l, r;bool isprime[maxm];int vis[maxm], cnt, prime[maxm], num[maxm];long long sum[maxm];int maxv;void init() { for (int i = 0; i <= maxv; i++) isprime[i] = true; for (int i = 2; i <= maxv; i++) { if (!isprime[i]) continue; if (vis[i]) num[i]+=vis[i]; prime[++cnt] = i; for (int j = i * 2; j <= maxv; j += i) { if (vis[j]) num[i] += vis[j]; isprime[j] = false; } }}int main() { maxv = 0; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); vis[a[i]]++; maxv = max(maxv, a[i]); } init(); for (int i = 1; i <= maxv; i++) sum[i] = sum[i-1] + num[i]; scanf("%d", &m); while (m--) { scanf("%d %d", &l, &r); if (l > maxv) { printf("0\n"); continue; } if (r > maxv) r = maxv; printf("%lld\n", sum[r] - sum[l - 1]); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。