TopCoder SRM 599 Div2 Medium BigFatInteger2

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";
	}
};

まとめ

境界条件にはちゃんと気を付けないとな。