E. Not a Nim Problem
Two players, Alice and Bob, are playing a game. They have $n$ piles of stones, with the $i$-th pile initially containing $a_i$ stones.
On their turn, a player can choose any pile of stones and take any positive number of stones from it, with one condition:
- let the current number of stones in the pile be $x$. It is not allowed to take from the pile a number of stones $y$ such that the greatest common divisor of $x$ and $y$ is not equal to $1$.
The player who cannot make a move loses. Both players play optimally (that is, if a player has a strategy that allows them to win, no matter how the opponent responds, they will win). Alice goes first.
Determine who will win.
Input
The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
Each test case consists of two lines:
- the first line contains a single integer $n$ ($1 \le n \le 3 \cdot 10^5$);
- the second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^7$).
Additional constraint on the input: the sum of $n$ across all test cases does not exceed $3 \cdot 10^5$.
Output
For each test case, output Alice if Alice wins, or Bob if Bob wins.
Example
Input
3
3
3 2 9
4
3 3 6 1
5
1 2 3 4 5Output
Bob
Alice
Bob
解题思路
借这题学一下 SG 函数。SG 函数是解决像取石子这类博弈论问题的一大利器。
以取石子游戏为例，我们把每一堆石子可能发生的变化用 DAG 来表示，其中节点代表一个局面，边代表可以从一个局面转移到另一个局面。比如以本题的规则对 $3$ 堆石子 $[1,3,4]$ 进行游戏得到的 DAG 如下：
每个节点（局面）$u$ 的 SG 值就是其后继节点 $v_1, \ldots v_m$ 的 SG 值的 $\mathrm{mex}$ 值，即 $\mathrm{SG}(u) = \mathrm{mex}\{ \mathrm{SG}(v_1), \ldots, \mathrm{SG}(v_m) \}$，其中定义集合 $S$ 的 $\mathrm{mex}$ 值为不属于 $S$ 中的最小非负整数。上图中每个节点的 SG 值如下所示：
可以发现每一个 DAG 都只有一个起点 $S$，因此如果 $\mathrm{SG}(S) \ne 0$ 则先手必胜，否则 $\mathrm{SG}(S) = 0$ 则先手必败。这是因为任意 SG 不为 $0$ 的节点都可以走到 SG 为 $0$ 的节点，而任意 SG 为 $0$ 的节点都走不到 SG 不为 $0$ 的节点（否则当前节点的 SG 值就大于 $0$ 了），又因为所有的终点（即出度为 $0$ 的点）的 SG 值为 $0$，对应着先手必败，因此结论得证。
而如果有 $n$ 个 DAG，每个 DAG 的起点分别为 $S_1, \ldots, S_n$，那么整个游戏先手必胜的条件是 $\mathrm{SG}(S_1) \oplus \cdots \oplus \mathrm{SG}(S_n) \ne 0$，否则 $\mathrm{SG}(S_1) \oplus \cdots \oplus \mathrm{SG}(S_n) = 0$ 则先手必败。证明的方法与 Nim 游戏十分相似。
回到本题，令 $A = \max\{ a_i \}$，显然我们需要求出 $1 \sim A$ 的 SG 值，然后根据 $\mathrm{SG}(a_1) \oplus \cdots \oplus \mathrm{SG}(a_n)$ 判断先手必胜还是必败，时间复杂度为 $O(A^2 \log{A})$。由于 $A$ 最大取 $10^7$，因此这种做法显会然超时。
我们先打表看看 SG 值是否满足某些规律，以下是求出 $1 \sim 100$ 的 SG 值的程序和结果：
打表代码
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int f[N];
int dfs(int u) {
if (f[u] != -1) return f[u];
set<int> st;
for (int i = 1; i <= u; i++) {
if (__gcd(i, u) == 1) st.insert(dfs(u - i));
}
for (int i = 0; true; i++) {
if (!st.count(i)) return f[u] = i;
}
}
int main() {
memset(f, -1, sizeof(f));
for (int i = 1; i <= 100; i++) {
cout << "SG(" << i << ") = " << dfs(i) << '\n';
}
return 0;
}打表结果
SG(1) = 1
SG(2) = 0
SG(3) = 2
SG(4) = 0
SG(5) = 3
SG(6) = 0
SG(7) = 4
SG(8) = 0
SG(9) = 2
SG(10) = 0
SG(11) = 5
SG(12) = 0
SG(13) = 6
SG(14) = 0
SG(15) = 2
SG(16) = 0
SG(17) = 7
SG(18) = 0
SG(19) = 8
SG(20) = 0
SG(21) = 2
SG(22) = 0
SG(23) = 9
SG(24) = 0
SG(25) = 3
SG(26) = 0
SG(27) = 2
SG(28) = 0
SG(29) = 10
SG(30) = 0
SG(31) = 11
SG(32) = 0
SG(33) = 2
SG(34) = 0
SG(35) = 3
SG(36) = 0
SG(37) = 12
SG(38) = 0
SG(39) = 2
SG(40) = 0
SG(41) = 13
SG(42) = 0
SG(43) = 14
SG(44) = 0
SG(45) = 2
SG(46) = 0
SG(47) = 15
SG(48) = 0
SG(49) = 4
SG(50) = 0
SG(51) = 2
SG(52) = 0
SG(53) = 16
SG(54) = 0
SG(55) = 3
SG(56) = 0
SG(57) = 2
SG(58) = 0
SG(59) = 17
SG(60) = 0
SG(61) = 18
SG(62) = 0
SG(63) = 2
SG(64) = 0
SG(65) = 3
SG(66) = 0
SG(67) = 19
SG(68) = 0
SG(69) = 2
SG(70) = 0
SG(71) = 20
SG(72) = 0
SG(73) = 21
SG(74) = 0
SG(75) = 2
SG(76) = 0
SG(77) = 4
SG(78) = 0
SG(79) = 22
SG(80) = 0
SG(81) = 2
SG(82) = 0
SG(83) = 23
SG(84) = 0
SG(85) = 3
SG(86) = 0
SG(87) = 2
SG(88) = 0
SG(89) = 24
SG(90) = 0
SG(91) = 4
SG(92) = 0
SG(93) = 2
SG(94) = 0
SG(95) = 3
SG(96) = 0
SG(97) = 25
SG(98) = 0
SG(99) = 2
SG(100) = 0可以发现以下规律：
- 如果 $x$ 是偶数，那么 $\mathrm{SG}(x) = 0$。
- 如果 $x$ 是从 $3$ 开始的质数，那么 $\mathrm{SG}(x) = p(x)$，其中 $p(x)$ 指 $x$ 在所有质数中的第几个。
- 如果 $x$ 是奇合数，那么 $\mathrm{SG}(x) = \mathrm{SG}(d(x))$，其中 $d(x)$ 指 $x$ 的最小质因子。
- 特别的，$\mathrm{SG}(1) = 1$，$\mathrm{SG}(2) = 0$。
因此我们就可以用欧拉筛以 $O(A)$ 的复杂度求出 $1 \sim A$ 的 SG 值。
AC 代码如下，时间复杂度为 $O(A)$：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e7 + 5;
int primes[N], cnt;
bool vis[N];
int f[N];
void get_prime(int n) {
for (int i = 2; i <= n; i++) {
if (!vis[i]) {
primes[cnt++] = i;
f[i] = cnt;
}
for (int j = 0; primes[j] * i <= n; j++) {
int t = primes[j] * i;
vis[t] = true;
if (t & 1) f[t] = f[primes[j]];
if (i % primes[j] == 0) break;
}
}
f[1] = 1, f[2] = 0;
}
void solve() {
int n;
cin >> n;
int ret = 0;
while (n--) {
int x;
cin >> x;
ret ^= f[x];
}
cout << (ret ? "Alice" : "Bob") << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
get_prime(N - 1);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
参考资料
第四章 数学知识（四）：https://www.acwing.com/file_system/file/content/whole/index/content/4810/
公平组合游戏 - OI Wiki：https://oi-wiki.org/math/game-theory/impartial-game/
Educational Codeforces Round 169 Editorial：https://codeforces.com/blog/entry/132790
标签：10,le,Nim,int,Problem,SG,节点,mathrm From： https://www.cnblogs.com/onlyblues/p/18364766