yukicoder No.2 素因数ゲーム

No.2 素因数ゲーム - yukicoder

問題概要

からはじめて、二人交互に、素因数を一つ決めて任意回数ずつ割っていく。先に にした人の勝ち。

解法

典型。素因数分解した後、NimのXOR判定条件を用いる。

struct Factor {
    inline vector<ll> factorize(ll N) {
        vector<ll> A;
        while (N != 1) {
            inc(i, 2, sqrt(N)) {
                if (N % i == 0) {
                    A.push_back(i);
                    N /= i;
                    goto next;
                }
            }
            A.push_back(N);
            break;
        next:;
        }
        sort(all(A));
        return A;
    }
}

int main() {
    ll N, res = 0;
    cin >> N;
    Factor F;
    vector<ll> A = F.factorize(N);
    map<ll, ll> M;
    rep(i, A.size()) M[A[i]]++;
    each(i, M) res ^= i.se;
    cout << (res ? "Alice" : "Bob") << endl;
}