SRM 664 Div1 Easy - BearPlays
問題
TopCoder Statistics - Problem Statement
問題概要
石を積んだ柱が2本ある。最初は片方に個、もう一方に個積まれている。次のような操作を回繰り返す:
- 石が少ない方に、多い方から少ない方の数と同じぶんを持ってくる(つまり、X<=Yのとき、Y-=X,X+=X)。
回の操作が行われた後の少ない方の石の個数を答えよ。
アイデア
とする。すると、石は片方からもう一方に何個か移動するのが1回の操作なので、片方の石の個数がなら、もう片方はとなる。そして、1回の操作によって個の方はになる(これは、ならそのままになるし、ならということである)。
ここまでわかると、現在の状態から2回操作したものはから、つまりはということになる。ここから、回後の操作によって個の方はになると考えられる。は非常に大きいが、繰り返し二乗法を使うことによって早く求めることが出来る。
実装(C++)
class BearPlays { public: int pileSize(int A, int B, int K) { ll s=A+B; ll p2[32]; p2[0]=2; for(int i=1; i<32; ++i) p2[i]=(p2[i-1]*p2[i-1])%s; ll ret=A; rep(i,32) { if(K>>i&1) { ret*=p2[i]; ret%=s; } } ret=min(ret,s-ret); return (int)ret; } };