kmjp's blog

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

TopCoder SRM 657 Div2 Hard PolynomialRemainder

シンプルな問題文。
http://community.topcoder.com/stat?c=problem_statement&pm=13774

問題

3つの整数a,b,cが与えられる。
 P(x)=ax^2+bx+cとするとき、 P(x)%10^9==0となる0以上10^9未満のxを1つ答えよ。

解法

最初自分は平方分割でゴリ押ししたが、その後Editorialを見たらスマートに解いていたので両方紹介。

自分の平方分割ゴリ押し法は以下の通り。
xを0以上10^6未満の範囲で総当たりし、P(x)の下6桁が0になるものを探す。
xに10^6を加えてもP(x)の下6桁は変わらないので、上記条件を満たすxに対し、10^6ずつ加算してP(x)の下9桁が0になるものを探す。

a,b,cが10^6の倍数だったりするとすべてのxでP(x)の下6桁が0になるので結局xを10^9通り全探索になりそうだが、幸いTLEせず通った。
ただこれはテストケースの運もあり、10^6のところを10^5にすると1.4s位のきわどいケースもあるようだ。

想定解は以下の通り。
10^9は(2^9)*(5^9)なので、0~2^9の範囲でP(y)%2^9==0になるyを探し、0~5^9の範囲でP(z)%5^9==0になるzを探す。
あとはCRTでも良いし、単に(z + k*(5^9)) % (2^9) == yとなるkを総当たりしてx = (z + k*(5^9))を求めても良い。
こちらは探索範囲が(5^9)通りなので余裕を持って通る。

以下両方のコード。

class PolynomialRemainder {
	public:
	
	int findRoot(int a, int b, int c) {
		ll mo=1000000000;
		int i;
		ll A=a, B=b, C=c;
		for(ll i=0;i<1000000;i++) {
			ll c=(i*i%mo*A + B*i + C)%mo;
			if(c%1000000) continue;
			for(ll j=i;j<mo;j+=1000000) if((j*j%mo*A + B*j + C)%mo==0) return j;
		}
		return -1;
	}
}

class PolynomialRemainder {
	public:
	
	int calc(ll a,ll b,ll c,ll m) {
		int i;
		for(i=0;i<m;i++) if((a*i%m*i+b*i+c)%m==0) return i;
		return -1;
	}
	
	int findRoot(int a, int b, int c) {
		ll p29=2*2*2*2*2*2*2*2*2;
		ll p59=5*5*5*5*5*5*5*5*5;
		ll p2=calc(a,b,c,p29);
		ll p5=calc(a,b,c,p59);
		
		if(p2==-1 || p5==-1) return -1;
		while(p5 % p29 != p2) p5+=p59;
		return p5;
	}
}

まとめ

コードは自分のゴリ押し解法の方が短いけど、考え方は想定解がスマートだね。