yukicoder 0002 素因数ゲーム
問題文概要
$2$人対戦ゲームをする. $N$ が与えられる. プレイヤーには交互にターンが回ってきて, 自分のターンになった時に, $p^e | N$ なる 素数 $p$ と正整数 $e$ を選び, $N$ を $N / (p^e)$ で更新する. $1$ にしたら勝ち.
先手後手のどちらが勝つか判定せよ.
制約
$1 \le N \le 10^8$.
解法
$N = \prod_{i=1}^{n} p_i ^ {e_i}$ と素因数分解すると, $\{e_1, \dots, e_n\}$ を山とする Nim をしている事になる.
ソースコード
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<int> factorization(int n){
vector<int> res;
for(int p = 2; p * p <= n; ++p) if(n % p == 0){
int e = 0;
for(; n % p == 0; ++e, n /= p);
res.emplace_back(e);
}
if(n != 1) res.emplace_back(1);
return res;
}
bool solve(){
int n;
cin >> n;
int nim = 0;
for(auto &x : factorization(n)) nim ^= x;
cout << (nim ? "Alice" : "Bob") << endl;
return true;
}