Div1 Easyよりちょっと面倒かも。
http://community.topcoder.com/stat?c=problem_statement&pm=12870
問題
数A,B,C,Dが与えられる。
A**BをC**Dで割り切れるか答えよ。
解法
AとCを素因数分解し、それぞれB・Dを掛けて素因数の乗数を求める。
全素因数について、A**Bの乗数がC**Dより大きければよい。
幾つかはまりポイントがある。
AとCを素因数分解する際、A,Cは10^9と大きいので√Aや√Cまで順次割っていくが、A,Cが素数だとどれでも割れない。
その場合A!=CかつC!=1ならA**BはC**Dで割れない。
自分が試したときはC!=1を見落として失敗した。
int NP,prime[100000]; const int prime_max = 1000000; void cprime() { static int p[prime_max]; int i,j; 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; } } ll aa[100000],cc[100000]; class BigFatInteger2 { public: string isDivisible(int A, int B, int C, int D) { int i,j,k; NP=0; cprime(); ZERO(aa); ZERO(cc); FOR(i,NP) if(A%prime[i]==0) { while(A%prime[i]==0) A/=prime[i],aa[i]+=B; } FOR(i,NP) if(C%prime[i]==0) { while(C%prime[i]==0) C/=prime[i],cc[i]+=D; } if(A!=C && C!=1) return "not divisible"; if(A!=1) aa[99999]=B; if(C!=1) cc[99999]=D; FOR(i,100000) if(aa[i]<cc[i]) return "not divisible"; return "divisible"; } };
まとめ
境界条件にはちゃんと気を付けないとな。