题解：CF2004E Not a Nim Problem
Mirage_Insane
·
·
题解
大致题意
给定 n 堆石子，第 i 堆有 a_i 个。对于每次操作，玩家可以选择任意一堆石子，设其还剩 x 个，若玩家可以从中取走 y 个，当且仅当 \gcd(x, y) 为 1。不能取石子的人输，问先手是否必胜。
题解
一眼博弈论，进一步发现属于公平组合游戏，于是转换成有向图游戏，使用 SG 定理。不会的戳这里。
考虑求出每个数的 SG 值。假设当前只有一个数，显然 0 先手必败；1 先手必胜；2 先手必败，因为先手只能取 1，然后后手就取完了。于是初始化：
SG(0) = 0,\ SG(1) = 1,\ SG(2) = 0
再设当前数为 x (x \geq 3)，当 x 为质数时，显然 y 可以是 1 到 x - 1 的任意数，有：
SG(x) = \operatorname{mex}_{y = 1} ^ {x - 1}\{SG(y)\}
进一步发现他的值就是他为第几个质数。
若 x 为合数，根据游戏的定义，有：
打表发现设 $x$ 最小的质因数为 $p$， 则 $SG(x) = SG(p)$。
用欧拉筛提前预处理出所有数的 SG 值，然后用 SG 定理就结束了。
### Code:
```cpp
#define Vanishment return
#define This 0
#define World ;
#include<bits/stdc++.h>
using namespace std;
#define SF scanf
#define PF printf
int sg[10000005], tot, a[10000005];
bool flag[10000005];
void init() {
sg[0] = 0;
for(int i = 2; i <= 10000000; i++) {
if(!flag[i]) a[++tot] = i, sg[i] = tot;
sg[1] = 1, sg[2] = 0;
for(int j = 1; j <= tot; j++) {
if(i * a[j] > 10000000) break;
flag[i * a[j]] = 1;
sg[i * a[j]] = sg[a[j]];
if(i % a[j] == 0) break;
}
}
}
int main() {
init();
int T;
SF("%d", &T);
while(T--) {
int n, x, ans = 0;
SF("%d", &n);
for(int i = 1; i <= n; i++) {
SF("%d", &x);
ans ^= sg[x];
}
PF(ans ? "Alice\n" : "Bob\n");
}
Vanishment This World
}
```