#include #include #include using namespace std; using namespace __gnu_pbds; int main(){ /***------------------------------------------ 素因子の種類と個数をそれぞれコインの山と見立てると Nimになって、すなわちGrundy数を計算すればよい ここで、1個のコインの山におけるNimは不偏ゲーム. NimはN個の山→N個の部分不偏ゲームから成るもので、 1個の部分不偏ゲームはコインの枚数そのものがGrundy数 Proof. (状態:コインの枚数Xに対してGrundy数を与える関数をG(x)とする) コイン0枚の山はゲーム終了状態なので、G(0)=0. コイン1枚で遷移できる状態は{0}なのでGのMEXを取ると1になって、G(1)=1. コイン2枚で遷移できる状態は{0,1}なのでGのMEXを取ると2になって、G(2)=2. 一般にコインk枚での遷移を考えると{0,1,...k-1}になるので、G(k)=k. □ ここで、N個の部分不偏ゲームそれぞれのGrundy数についてXORsumを取って、 それがzeroかnon-zeroかで勝敗が定まる. non-zeroなら先手必勝. --------------------------------------------***/ cin.tie(nullptr)->ios::sync_with_stdio(false); int N; cin>>N; gp_hash_table primes; for(int i=2;i*i<=N;i++){ while(N%i==0){ primes[i]++; N/=i; } } if(N!=1) primes[N]++; int xorsum=0; for(auto [_,c]:primes) xorsum^=c; cout<<(xorsum?"Alice\n":"Bob\n"); }