Codeforces 385C Bear and Prime Numbers(数论）

本文主要是介绍Codeforces 385C Bear and Prime Numbers(数论），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：Codeforces 385C Bear and Prime Numbers

题目大意：给出一个长度为n的序列，然后有m次询问，每次询问给出a， b，然后计算[a,b]中所有素数的F（x）之和，F（x）为计算序列中有几个数为x的倍数。

解题思路：数论题，因为内存空间限制为512M，所以可以开的下10^7的数组，然后用筛选法求素数的同时计算个数。

#include <stdio.h>
#include <string.h>const int N = 10000005;int n, m, v[N], g[N], s[N];void init() {memset(v, 0, sizeof(v));memset(g, 0, sizeof(g));memset(s, 0, sizeof(s));int a;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &a);g[a]++;}for (int i = 2; i < N; i++) {if (v[i]) continue;for (int j = i; j < N; j += i) {if (g[j]) s[i] += g[j];v[j] = 1;}}for (int i = 1; i < N; i++) s[i] += s[i-1];
}void solve() {int a, b;scanf("%d", &m);for (int i = 0; i < m; i++) {scanf("%d%d", &a, &b);if (a >= N) a = N;if (b >= N) b = N - 1;printf("%d\n", s[b] - s[a-1]);}
}int main() {init();solve();return 0;
}

这篇关于Codeforces 385C Bear and Prime Numbers(数论）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---