裏紙

ほぼ競プロ、たまに日記

SRM 664 Div1 Easy - BearPlays

問題

TopCoder Statistics - Problem Statement

問題概要

石を積んだ柱が2本ある。最初は片方にA個、もう一方にB個積まれている。次のような操作をK回繰り返す:

  • 石が少ない方に、多い方から少ない方の数と同じぶんを持ってくる(つまり、X<=Yのとき、Y-=X,X+=X)。

K回の操作が行われた後の少ない方の石の個数を答えよ。

  •  1 \le A,B \le 10^9
  •  1 \le K \le 2*10^9

イデア

S=A+Bとする。すると、石は片方からもう一方に何個か移動するのが1回の操作なので、片方の石の個数がxなら、もう片方はy=S-xとなる。そして、1回の操作によってx個の方は2x \% Sになる(これは、x \le yならそのまま2xになるし、x \gt yならx-y = x(+x-x)-y=2x-Sということである)。

ここまでわかると、現在の状態から2回操作したものはxから2(2x \% S) \% S、つまりは4x \% Sということになる。ここから、K回後の操作によってx個の方は2^{K}x \% Sになると考えられる。Kは非常に大きいが、繰り返し二乗法を使うことによって早く求めることが出来る。

実装(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;
    }
};