シンプルな問題文。
http://community.topcoder.com/stat?c=problem_statement&pm=13774
問題
3つの整数a,b,cが与えられる。
とするとき、となる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; } }
まとめ
コードは自分のゴリ押し解法の方が短いけど、考え方は想定解がスマートだね。