素数取りゲーム [東京工業大学プログラミングコンテスト2019 D]

https://atcoder.jp/contests/ttpc2019/tasks/ttpc2019_d

前提知識

• grundy数

解説

https://atcoder.jp/contests/ttpc2019/submissions/7225749

以下、grundy数の理解が必須。
太字のルール「一度に取ることができる石の数は素数個で、かつその山の残る石の数も0個または素数個である必要がある」
特殊なルールであるが、素数1-X=素数2となるのは「X=素数1」か「X=2」か「Xが素数1-2の素数」となるかしかない。
つまり、遷移は多くて3択になる。
遷移が3つであれば、grundy数が事前計算できるので、計算しよう。
あとは、全ての山のgrundy数をxorして、判定する。

int N, A[201010];
int grundy[1010101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    auto pr = makePrimesBool(1010101);
    rep(i, 1, 1010101) if(pr[i]) {
        set<int> gr;
        gr.insert(0); // get i
        if (0 < i - 2 and pr[i - 2]) {
            gr.insert(grundy[i - 2]); // get 2
            gr.insert(grundy[2]); // get i-2
        }
        while(gr.count(grundy[i])) grundy[i]++;
    }

    int xo = 0;
    rep(i, 0, N) xo ^= grundy[A[i]];

    if(xo == 0) cout << "Ai" << endl;
    else cout << "An" << endl;
}