Codeforces 385(#226 Div2 only) C. Bear and Prime Numbers
問題
n項からなる数列x[i]が与えられる。
素数pに対してf(p)は、xのうちpの倍数であるものの個数とする。
[l, r]が与えられるので、l以上r以下の素数p全てについてf(p)の和を求めよ、
というクエリがm個くるので答えよ。
制約条件
n≦10^6
m≦50000
x[i]≦10^7
l, r≦10^9
方針
x[i]を素因数分解しつつpで割れたらsum[p]に1を足す。
で、この累積和を計算すれば、l, rのクエリに対してsum[r] - sum[l - 1]を計算すれば、
クエリに対してはO(1)で答えを出すことができる。
ソースコード
const int MX = 10001000; int n, m; int p[MX], sum[MX]; int main(){ for(int i = 2; i < MX; i++){ if(p[i]) continue; p[i] = i; for(ll j = (ll)i * i; j < MX; j += i) p[j] = i; } cin >> n; rep(i, n){ int a; cin >> a; while(a > 1){ int b = p[a]; sum[b]++; for(; a % b == 0; a /= b); } } rep(i, 10001000 - 1) sum[i + 1] += sum[i]; cin >> m; while(m--){ int l, r; cin >> l >> r; r = min(r, 10001000 - 1); l = min(l, r); cout << sum[r] - sum[l - 1] << endl; } return 0; }