SRM 664 Div1 Easy Bear Plays

組(X,Y)(X <=Y)を一回操作して(2X,Y-X)にするとき、石の総量S = X + Y は変化しない。よって、少ない方の個数がXのとき、一回の操作後に得られる組の少ない方の個数f(X)は

f(X) = 2X or S - 2X

これをmod S で見ると、f(X) ≡ 2X or -2X であるから、f^K (X) ≡ 2^K * X or -2^K * X

f^K (X) ≡ -2^K * X は個数がS - 2^K * X の場合に対応するから、X = min(A,B)として、min(2^K * X, S - 2^K * X) (mod S) が答えとなる。

#include <bits/stdc++.h>
using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(int)(b);++i)
#define REP(i,n) FOR(i,0,n)

typedef long long ll;

class BearPlays{
public:
  ll modpow(ll K, ll S){
    if(K == 0)return 1;
    if(K % 2) return (2 * modpow(K - 1, S)) % S;
    return (modpow(K/2, S) * modpow(K/2, S)) % S;
  };
  int pileSize(int A, int B, int K){
    ll S = A + B;
    A = min(A, B);
    ll res = (A * modpow(K,S)) % S;
    return min(res, S - res);
  };
};