SRM664 Div1 Easy BearPlays

2015/08/02 (Sun) SRM 数学

問題

問題文

自然数の組 $(X,Y)$ が与えられる．$X\leq Y$ なら $(2X,Y-X)$ に，そうでなければ $(X-Y,2Y)$ に置き換えるという操作を $K$ 回繰り返す．その後の $X,Y$ のうち小さい方を求めよ．

方針

$S=X+Y$ として $\mathrm{mod}\ S$ で考える．

  • $X \leq Y$ のとき $X \to 2X$
  • $X>Y$ のとき $X \to X-Y = X-(S-X) = 2X-S = 2X$

になるので，いずれにせよ $\mathrm{mod}\ S$ で $2$ 倍にしてるだけ． $K$ 回繰り返せば $2^K$ 倍になるので，結局 $X2^K$ が最終的な $X$ の値になる． そのときの $Y$ は $S-X$ となるので， $\min(X,S-X)$ を返す． $K$ 乗の部分は繰り返し二乗法で高速に求める．

実装

class BearPlays {
public:
    ll A,B,K;
    int pileSize( int A_, int B_, int K_ ) {
        A = A_;
        B = B_;
        K = K_;
        ll S = A+B;
        ll res1 = A*modpow(2,K,S)%S;
        ll res2 = S-res1;
        return min(res1,res2);
    }
    ll modpow(ll a, ll b, ll m){
        if(b==0) return 1;
        ll x = modpow(a,b/2,m);
        ll res = x*x%m;
        return (b&1)==1 ? res*a%m : res;
    }
};