Yukicoder002 素因数ゲーム

問題概要

$N$が与えられる。( $N\leqq10^8$ )

2人で次のゲームを行う。 $N$の素因数を一つ選択し、相手に$N$をその素因数で割った商を新たな$N$として渡す。 このとき同じ数であれば何回割っても良い。 先手後手どちらが勝つか。

yukicoder002

解法

基本となる素数を$Nim$の山として、ある素数の数はある$Nim$の山の石の数に対応する。 素因数は $sqrt(N)$で、 $Nim$は素因数の各個数を列挙したものの$XOR$を取ればよい。

$Nim$ってなんだと言う人はこちらへ。 競プロにおけるNim、Grundy数とNimK

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    using VI = vector<int>;       using VVI = vector<VI>;
    #define SZ(a) int((a).size())
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    
    
    LL N;
    
    LL ans = 0LL;
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        cin >> N;
        VI a;
        LL NN = N;
        for (int i = 2; i*i <= NN; i++) {
            int cnt = 0;
            while (N%i == 0) {
                cnt++;
                N /= i;
            }
            if (cnt)a.push_back(cnt);
        }
        if (N > 1) {
            a.push_back(1);
        }
        FOR(i, 0, SZ(a)) {
            ans ^= a[i];
        }
    
    
        cout << (ans == 0 ? "Bob" : "Alice") << "\n";
    
        return 0;
    }