SRM664 Div1.Easy BearPlays

この前TopCoderやってみたらDiv1に上がったのでとりあえずDiv1.Easy解いてみてなるほど、ってなったのだけ書いていきます。

A,Bという数字が与えられて、A<=BならAをA*2, BをB-Aに更新していく問題。
試行回数がK=2000000000なので計算時間を短縮しなければいけない。
最初、何の根拠も無しにA,Bのpairをmapに保存して同じのが来たらうんちゃらかんちゃらしてみたけど案の定TLE。
でもそれ以上なにも浮かばなかった…。

実際は、A<=BでもA>Bでも、どちらかをとりあえず二乗してmod(A+B)をとってあげれば1試行後のA,Bのどちらかになる。
これはA>BならA*2 = A+(A+B)-B = A-B(mod(A+B))より明らか。A+Bはずっと保存するので、AかBにmod(A+B)の2のK乗をかけてあげるだけで答えが出る。

まとめるとかそういうことばっか考えてたけど、こういうふうに数学的な感じで解く問題もあるのだなぁ…。

class BearPlays {
public:
    ll ruijo(ll x, ll n, ll mod){
        ll res = 1;
        while(n > 0){
            if(n&1) res = res *x % mod;
            x = x * x % mod;
            n >>= 1;
        }
        return res;
    }

    int pileSize( int A, int B, int K ) {
        ll tmp = min((ll)A, (ll)B)*ruijo(2, K, A+B)%(A+B);
        return min(A+B-tmp, tmp);
    }
};