No.103 素因数ゲームリターンズ

最初 grundy 数とか計算してたけど、素数を山の種類、冪を山の高さとする Nim と考えと素因数分解して xor を取るだけだった。
初期状態で決まる勝ち負け状態を保ったまま山の高さを k%3 まで遷移させることができるので、最初から山が k%3 だと考えてよい。

class PrimeGameReturns {
public:
    void solve(void) {
            int N;
            cin>>N;
            int det = 0;

            REP(i,N)
            {
                int m;
                cin>>m;
                // 素数を山の種類、冪を山の高さとする Nim と考える
                auto primes = primeFactorize(m);
                for (auto pk : primes)
                {
                    int p,k;
                    tie(p,k) = pk;
                    // 初期の勝ち負け状態をたもったまま k%3 まで遷移させることができる
                    // (ある山から相手が 1(2) をとったら自分は 2(1) を取ればよい。)
                    det = det ^ (k % 3);
                }
            }
            if (det)
                cout<<"Alice"<<endl;
            else
                cout<<"Bob"<<endl;
    }
};