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); }; };