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

問題
No.103 素因数ゲーム リターンズ - yukicoder
個の整数が与えられる．
一度の操作で任意の整数をその素因数で割ることができる．同じ素因数ならば２回まで同時に割れる．
AliceとBobが交互に操作を行うとき，すべての整数をにできるのはどちらか．

解法
のgrundy数を求める．0を負けの状態，1,2を勝ちの状態とすると
(状態(状態(状態(状態(状態,...
としてルールに従うと，(状態0)から(状態0)にすることはできず，(状態1),(状態2)からは(状態0)にすることができるということが分かる．つまり，指数部を状態にすればよくなる．
と表すとき，grundy数はすべての の排他的論理和となる．後はすべてののgrundy数について排他的論理和をとれば勝敗がわかる．

ソースコード

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

#define REP(i,s,e) for (i = s; i <= e; i++)
#define rep(i,n) REP (i,0,(int)(n)-1)
#define RREP(i,s,e) for (i = s; i >= e; i--)
#define rrep(i,n) RREP (i,(int)(n)-1,0)
#define INF (int)1e8
#define MOD (int)(1e9+7)

typedef long long ll;

int main(void) {
    int i, j, n;
    int m[100], grundy[100];
    cin >> n;
    rep (i,n) cin >> m[i];
    rep (i,n) {
        map<int,int> mp;
        int x = m[i];
        for (j = 2; j * j <= x; j++) {
            if (x % j == 0) {
                mp[j]++;
                x /= j;
                j--;
            }
        }
        mp[x]++;
        grundy[i] = 0;
        for (auto p : mp)
            grundy[i] ^= p.second % 3;
    }
    int ans = 0;
    rep (i,n) ans ^= grundy[i];
    if (ans == 0)
        cout << "Bob" << endl;
    else
        cout << "Alice" << endl;
    return 0;
}