kmjp's blog

競技プログラミング参加記です

Codeforces #226 Div2. C. Bear and Prime Numbers

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]);
	}
}

まとめ

素因数分解で事前に素数を列挙するのが無駄だな…。
P<=10^6なら√P掛けて素因数分解しても良かったのだけど。