Codeforces-2004E Not a Nim Problem
有 \(n\) 堆石子，数量为 \(a_1,\cdots,a_n\)，每次可以取走的数量 \(y\) 与原来的数量 \(x\) 必须满足 \(\gcd(x,y)=1\)。
不能行动的人判负。请判断 Alice（先手）和 Bob 谁会获胜。
\(1\le T\le10^4\)，\(1\le n,\sum n\le3\cdot10^5\)，\(1\le a_i\le10^7\)。
首先考虑只有一堆的情况，\(n\) 堆的情况直接利用 SG 定理，对 SG 值取异或和即可。
首先 \(x=1\) 为必胜状态。\(x=2\) 为必败状态，因为只能拿 \(1\) 个。从而 \(x=3\) 为必胜状态，因为可以转移到 \(2\)。
数学归纳法：假设 \(x=2k\) 都为必败状态，\(x=2k-1\) 都为必胜状态，\(k=1,2,\cdots\)。那么 \(x=2k+1\) 时，由于 \(\gcd(2k+1,1)=1\)，因此可以转移到 \(2k\)，是必胜状态；\(x=2k+2\) 时，只能转移到奇数，因此是必败状态。
综上，对于单独一堆石子，奇数必胜，偶数必败。
然而对 \(n\) 堆石子，我们还需要考虑每一堆的 SG 值。
由于 \(\gcd(x,x-y)=\gcd(x,y)\)，所以 \(x\) 能转移到 \(x-y\) 当且仅当 \(\gcd(x,x-y)=1\)。
写出前几个奇数的 SG 函数：
| 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 | 23 | 25 | 27 | …… |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 2 | 5 | 6 | 2 | 7 | 8 | 2 | 9 | 3 | 2 | …… |
注意到，如果奇数 \(x\) 是第 \(s\) 个质数，那么 \(SG(x)=s\)；否则设 \(y\) 为 \(x\) 的最小质因数，那么 \(SG(x)=SG(y)\)。特别地，\(SG(1)=1\)。
这种规律的意义是显然的（\(y\) 是 \(x\) 第一个无法转移的数，根据 SG 函数的定义，\(SG(x)\) 为可转移的状态集合的 SG 的 mex）。
可以利用数学归纳法来严格证明，这里省略。
由此，我们可以利用筛法（埃氏筛或线性筛）求出所有数的 SG 值，再进行异或即可。
当然，不管是埃氏筛还是线性筛，我们只筛奇数就可以了。
void init() { // 埃氏筛SG[1] = 1;int cnt = 1;for (int i = 3; i <= 10000000; i += 2) {if (!vis[i]) {SG[i] = ++cnt;if ((long long)i * i > 10000000) continue;for (int j = i * i; j <= 10000000; j += i * 2) {if (!SG[j]) SG[j] = cnt;vis[j] = true;}}}return;
}
void init() { // 线性筛SG[1] = 1;int cnt = 1;for (int i = 3; i <= 10000000; i += 2) {if (!vis[i] && (i & 1)) pri[SG[i] = ++cnt] = i;for (int j = 2; j <= cnt && i * pri[j] <= 10000000; j++) {vis[i * pri[j]] = true;SG[i * pri[j]] = SG[pri[j]];if (i % pri[j] == 0) break;}}return;
}