E. Not a Nim Problem 完整题解（基于标程）

---

一、题目重述

有 $n$ 堆石子，第 $i$ 堆初始有 $a_i$ 个石子。
两人轮流操作，Alice 先手。
每回合，玩家选择一堆石子，设当前该堆有 $x$ 个石子，可以取走 $y$ 个石子（$1 \le y \le x$），但要求 $\gcd(x, y) = 1$。
无法操作的玩家输。

问：双方都采取最优策略时，谁获胜？

数据范围：$n$ 总和 $\le 3\times 10^5$，$a_i \le 10^7$。

---

二、转化为 impartial 博弈

这是一个 impartial 组合游戏（双方操作相同），可以用 Sprague–Grundy 定理求解：

• 整个游戏的 SG 值为各堆 SG 值的异或和：$$\text{SG}_{\text{total}} = \bigoplus_{i=1}^n g(a_i) $$
• 若 $\text{SG}_{\text{total}} \neq 0$，则先手（Alice）获胜；否则 Bob 获胜。

因此，问题转化为：计算每个正整数 $x$ 的 Grundy 数 $g(x)$。

---

三、单堆游戏的 Grundy 数定义

对于一堆 $x$ 个石子，定义 $g(x)$ 为它的 Grundy 数：

$$g(x) = \text{mex} \{\, g(x - y) \mid 1 \le y \le x,\ \gcd(x, y) = 1 \,\} $$

其中 $\text{mex}$ 表示最小的非负整数不在集合中。

边界条件：$g(0) = 0$（没有石子，无法操作）。

---

四、标程的核心结论

标程中 grundy(x) 函数的计算逻辑是：

int grundy(int x) {
    if (x == 1) return 1;
    int cnt = 0;
    int last = 0;
    while (x > 1) {
        int p = spf[x];
        if (p != last) {
            cnt++;
            last = p;
        }
        x /= p;
    }
    return cnt % 2;
}

这个函数计算的是：$x$ 的不同质因数个数（$\omega(x)$）的奇偶性，并对 $x=1$ 特殊处理为 $1$。

即：

$$g(x) = \begin{cases} 1, & \text{if } x = 1 \\ \omega(x) \bmod 2, & \text{if } x > 1 \end{cases} $$

其中 $\omega(x)$ 表示 $x$ 的不同质因数的个数。

---

五、验证小数据

我们手工计算 $\omega(x)$ 并对比之前的小范围 Grundy 值，验证这个结论是否正确。

$x$	$\omega(x)$	$\omega(x) \bmod 2$	标程 $g(x)$	之前手工计算 $g(x)$
1	0		1（特判）	1
2	1			0 ❌

发现矛盾：$x=2$ 时，手工计算 $g(2)=0$，但标程返回 $1$。
难道是标程错了？不，标程能通过本题，说明本题的 Grundy 数定义可能与我们手工计算的不同？或者手工计算有误？

重新手工计算 $g(2)$：

• $x=2$，可取的 $y$：必须满足 $\gcd(2,y)=1$，所以 $y$ 只能是奇数且 $1 \le y \le 2$，即 $y=1$。
• 到达状态 $2-1=1$，$g(1)$ 是多少？需要先确定 $g(1)$。
• $x=1$，可取 $y=1$（$\gcd(1,1)=1$），到达 $0$，$g(0)=0$，所以 $g(1)=\text{mex}\{0\}=1$。
• 因此 $g(2)=\text{mex}\{g(1)\}=\text{mex}\{1\}=0$。

手工计算没错。那么标程为何返回 $1$？唯一解释：本题的博弈规则中，从 $x=2$ 时是否允许取 $y=2$？
条件：$\gcd(x,y) \neq 1$ 才不允许，即 $\gcd(x,y)=1$ 允许。
$\gcd(2,2)=2 \neq 1$，所以不允许。所以手工计算正确。

但标程能 AC，说明实际通过的代码中，对于偶数的处理可能不同。再检查标程：它用的是 cnt % 2，对于 $x=2$，不同质因数个数 $\omega(2)=1$，$1\%2=1$，但实际答案是 $0$。
这只能说明：标程中的 grundy 并非直接返回 $\omega(x) \bmod 2$，而是有其他含义。

仔细看标程：它统计的是不同质因数的个数 cnt，然后返回 cnt % 2。对于 $x=2$，cnt=1，返回 $1$。
但根据题目样例，第一个样例 3 2 9 输出 Bob，说明异或和为 $0$。
计算：$g(3)$ 按此公式：$\omega(3)=1$，返回 $1$；$g(2)=1$；$g(9)$：$9=3^2$，不同质因数 $\{3\}$，cnt=1，返回 $1$。异或和 $1 \oplus 1 \oplus 1 = 1 \neq 0$，会输出 Alice，但样例输出是 Bob，矛盾。

这说明：标程可能不是用这个公式？或者我误解了样例？
再检查样例1：3 2 9 输出 Bob。若 $g(3)=2$（手工算得），$g(2)=0$，$g(9)=2$，异或 $2 \oplus 0 \oplus 2 = 0$，输出 Bob 正确。
所以标程的 cnt % 2 肯定不对。

结论：你给的标程可能是错误的，或者它是针对另一个题目的。
但既然你要求根据这个标程写题解，我就基于它的逻辑来解析。

---

六、基于标程的正确结论（假设标程正确）

标程的核心是：

$$g(x) = \begin{cases} 1, & x = 1 \\ \omega(x) \bmod 2, & x > 1 \end{cases} $$

其中 $\omega(x)$ 是 $x$ 的不同质因数个数。

那么整个游戏的 SG 值就是所有 $a_i$ 的 $\omega(a_i) \bmod 2$ 的异或和，并特判 $a_i=1$ 时为 $1$。

---

七、算法步骤

1. 预处理：用埃氏筛或线性筛计算 $10^7$ 以内每个数的最小质因子 spf[x]。
2. 计算 $\omega(x)$：
   • 若 $x=1$，直接返回 $1$。
   • 否则，利用 spf 分解 $x$，统计不同质因数的个数 cnt，返回 cnt % 2。
3. 合并：对于每个测试用例，计算所有 $a_i$ 的 Grundy 数的异或和。
4. 判断：若异或和非零，输出 "Alice"，否则输出 "Bob"。

---

八、复杂度分析

• 筛法：$O(M \log \log M)$，$M = 10^7$。
• 每个数分解：$O(\log a_i)$，总 $O(\sum \log a_i)$。
• 总复杂度满足要求。

---

九、最终代码（即你给出的标程）

#include <bits/stdc++.h>
using namespace std;

const int N = 1e7 + 5;
int spf[N]; // smallest prime factor

void sieve() {
    for (int i = 2; i < N; ++i) {
        if (spf[i] == 0) {
            spf[i] = i;
            for (int j = i * 2; j < N; j += i) {
                if (spf[j] == 0) spf[j] = i;
            }
        }
    }
}

int grundy(int x) {
    if (x == 1) return 1;
    int cnt = 0;
    int last = 0;
    while (x > 1) {
        int p = spf[x];
        if (p != last) {
            cnt++;
            last = p;
        }
        x /= p;
    }
    return cnt % 2;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    sieve();
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int xr = 0;
        for (int i = 0; i < n; ++i) {
            int a;
            cin >> a;
            xr ^= grundy(a);
        }
        cout << (xr ? "Alice" : "Bob") << '\n';
    }
    
    return 0;
}