Codeforces 385C Bear and Prime Numbers(素数击表,二分)
Codeforces 385C Bear and Prime Numbers(素数打表,二分)
题意:给出n个数,m次查询,每次查询一个区间[l,r],求n个数中是区间[l,r]之间素数倍数的个数和,每个素数都要算一次和.
解法:由于Xi最大为10^7,所以可以开一个这么大的数组,用筛选法求出素数和对应的和,最后查询的时候二分找素数位置.
#include <cstdio> #include <memory.h> #include <algorithm> using namespace std; const int MAX = 10000001; int bucket[MAX]; int prime[MAX / 10]; bool is_prime[MAX]; int S[MAX / 10]; int n, m, max_prime, p_idx; void generate_prime(){ memset(is_prime + 2, true, sizeof(is_prime)); p_idx = 1; for(int i = 2; i <= max_prime; ++i){ if(is_prime[i]){ prime[p_idx] = i; S[p_idx] = S[p_idx - 1] + bucket[i]; for(int j = i + i; j <= max_prime; j += i){ is_prime[j] = false; S[p_idx] += bucket[j]; } ++p_idx; } } } int main(int argc, char const *argv[]){ scanf("%d", &n); for(int i = 0; i < n; ++i){ int v; scanf("%d", &v); ++bucket[v]; max_prime = max(max_prime, v); } generate_prime(); scanf("%d", &m); while(m--){ int l, r; scanf("%d%d", &l, &r); int lp = lower_bound(prime + 1, prime + p_idx, l) - prime; int rp = lower_bound(prime + 1, prime + p_idx, r) - prime; if(rp == p_idx)--rp; if(prime[rp] > r){ --rp; } printf("%d\n", S[rp] - S[lp - 1]); } return 0; }