Div2回のCF#226に参加。
A,B,C,Dを何とか解いたけど、Eは時間切れ。方針はあっていたがバグがとりきれず、systest中に正答にたどり着いた。
http://codeforces.com/contest/385/problem/C
問題
N個の自然数X[i]が与えられる。
さらにM個のクエリが与えられる。
各クエリはL[i],R[i]の2整数で表現される。
各クエリの解は、L[i]~R[i]の区間に含まれる各素数について、X[i]を割り切る数の総和である。
これらのクエリについて答えよ。
解法
前処理をしておくことで、各クエリO(1)で処理していく。
事前にX[i]を素因数分解しておき、X[i]を割り切る素数の数を列挙しておく。
後はその数の総和を取っておけば、よい。
X[i]の上限をPとするとP<=10^7なので、素因数分解を単純に1~√Pで割っていこうとするとO(N√P)はTLEになる。
事前に素数の一覧を作っておくとよい。
素数作成がO(√P)、素因数分解がO(N logP)、クエリ処理がO(M)で、素因数分解が一番重いけどなんとか間に合う。
L,Rの範囲が地味に大きいので、P以上のものは無視するようにしないと配列外アクセスしてRuntime Errorになるので注意。
int N,M; ll NN[10000010]; ll SUM[10000010]; int NP,prime[10000]; const int prime_max = 10000; void cprime() { static int p[prime_max]; int i,j; NP=0; for(i=2;i<prime_max;i++) { if(p[i]) continue; prime[NP++]=i; for(j=i*2;j<prime_max;j+=i) p[j]=i; } } void solve() { int f,i,j,k,l,x,y; cprime(); cin>>N; FOR(i,N) { cin>>x; FOR(j,NP) { if(prime[j]*prime[j]>x) break; if(x%prime[j]==0) { NN[prime[j]]++; while(x%prime[j]==0) x/=prime[j]; } } if(x!=1) NN[x]++; } FOR(i,10000001) SUM[i+1]=SUM[i]+NN[i+1]; cin>>M; FOR(i,M) { cin>>x>>y; if(x>10000000) { _P("0\n"); continue; } if(y>10000000) y=10000000; _P("%lld\n",SUM[y]-SUM[x-1]); } }