将该组合游戏进行拆解，某个 DAG 上该游戏先手必胜等价于 $1,2$ 节点的 SG 值不相等。

某个节点的 SG 值为其所有后继节点的 $\mathrm{mex}$，也即某个节点的 SG 值为 $x$ 当且仅当其向 SG 值分别为 $[0,x)$ 的节点各连了至少一条边，并且没有连向 $x$ 的边。

这提示我们从小到大，每次考察 SG 值为 $x$ 的点的集合。SG 值大于 $x$ 的所有节点必须向这个集合中至少连一条边；这个集合中的节点不能向集合中其它节点连边；SG 值小于 $x$ 的所有节点连边无限制。

状压 DP 即可。

鉴于每次只能选择一个质因数取，我们可以将原游戏分解为多个游戏的组合，对于质数 $p$，若 $a_i=p^{\alpha_i}k_i$（其中$p\not\mid k_i$），那么 $p$ 对应的游戏为：

对于集合 $\{\alpha_1,\alpha_2,\cdots,\alpha_n\}$，每次选择正整数 $k$，将集合中所有不小于 $k$ 的数全部减去 $k$，直到所有数全部变为 $0$。

由于 $n\le10^9$，$\alpha_i$ 不超过 $30$，可以状压。状态数上界不会证。

于是可以通过动态规划求出每个 $p$ 对应的游戏，每个状态的 SG 值。通过 SG 定理可以求得原问题起点的 SG 值。

博弈相关定义参考：博弈论简介 - OI Wiki

性质与定义

我们抛开这个游戏的任何实质性内容（规则、状态），只着眼于每个状态所构成的图结构。

那么任何游戏都可以看作是“某个标记沿着图上的边移动”的过程。

并且对于公平组合游戏，我们只需知道这个图的构造，我们就可以依照下面两条显然的性质判定每个点是必胜点还是必败点。

• 如果后继所有点都为必胜点，那么这个点为必败点
• 否则这个点为必胜点

我们也可以根据这两个条件互为否定得出，这个图上的每个点一定是必胜点或必败点之一。

并且我们可以用某个点的所有后继节点（亦作为一个集合）构成的集合，形式化地描述任意一个 DAG 上的所有点。

那么两个能够由 DAG 描述的游戏的复合（这个游戏的每一步是在两个游戏中选一个进行）应当如下定义：

$$\displaylines{A+B=\{a+B\mid a\in A\}\cup\{A+b\mid b\in B\} }$$

SG 定理

所有的一般胜利条件下的公平组合游戏都能转换成 Nim 数表达的 Nim 游戏。

一个公平组合游戏的 Nim 数（即 SG 函数）定义为这个博弈的等价 Nim 数。

证明见 Sprague–Grundy theorem - Wikipedia。

典例

更多典例：博弈论小计 - command block。

Nim 游戏

当 $n$ 堆石子个数异或和为 $0$ 时该状态为必败状态，否则为必胜状态。

证明见 Nim 和 - OI Wiki。

K-Nim 游戏

SDOI2011 黑白棋

每次取石子的堆数在 $[1,d]$ 范围内。

将每个石子堆的个数写成二进制形式并右侧对齐，如果每一位之和都是 $d+1$ 的倍数则为必败态，否则为必胜态。

限制取子个数的 Nim 游戏

ABC297G

限制每次取的石子个数在 $[L,R]$ 范围内。

这个游戏的 SG 函数为

$$\displaylines{\left\lfloor\frac{x\bmod(L+R)}L\right\rfloor }$$

证明见 ABC297G Editorial。