自动搬运

查看原文

来自洛谷，原作者为

	MatrixGroup 删繁就简

搬运于2025-08-24 23:06:01，当前版本为作者最后更新于2024-11-16 16:41:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

前言

「经过数学家的不懈努力」是 Nim 积相关题解不可避免的一环……吗？

本文旨在勾勒部分 Nim 积性质的证明，有了这些性质后数据结构优化是不难的，可以参考其它题解。

更具体的介绍可以参考这篇文章（仍在更新中！）。

本文参考了《On Numbers And Games》的第六章。

对于不理解何为「序数」的读者，可以自行将文中所有「序数」换为「非负整数」。

如果你学过一定的抽象代数，你可以把文中的「对加法封闭」「对加法、乘法封闭」「对四则运算封闭」「所有多项式方程均有解」替换成「是群」「是环」「是域」「代数闭」。（因为异或意义下 $\alpha+\alpha=0$，一个数自然有相反数，因此可以不考虑减法）

在集合论中，冯诺依曼表示法的序数 $\alpha$ 就是集合 $\{\beta|\beta<\alpha\}$，其中 $\beta$ 是序数。本文不区分这两者。例如，当我们说到「$2$ 对四则运算封闭」的时候，也就是说「$\{0,1\}$（在异或和 Nim 积意义下）对四则运算封闭。」

本文中，方括号 $[]$ 中的运算为通常的序数运算，而其外部的运算为 Nim 运算。

引子

假如我们想在所有序数上定义一个加法和一个乘法，使得它们对四则运算封闭，并且它“字典序最小”（这个概念并不严格），应该怎么做？

先考虑加法吧。

$0+0=0$ 显然不会有问题，因此 $0$ 就是这个域上的零元。故而 $0+\alpha=\alpha+0=\alpha$。

$1+1=0$ 不会有问题，不就是特征【最小的 $n$ 满足所有数加 $n$ 遍等于 $0$】为 $2$ 嘛。

$1+2$ 是几？它不能等于 $1+1=0$，$1+0=1$，$0+2=2$，否则就和域有加法逆元（因此有消去律）矛盾了。因此 $1+2=3$。

这启发我们递归地定义

$$\alpha+\beta=\operatorname{mex}(\{\alpha+\delta|\delta<\beta\}\cup\{\gamma+\beta|\gamma<\beta\}) $$

据此列出表格

$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} +&0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15\\\hline 0&0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15\\\hline 1&1&0&3&2&5&4&7&6&9&8&11&10&13&12&15&14\\\hline 2&2&3&0&1&6&7&4&5&10&11&8&9&14&15&12&13\\\hline 3&3&2&1&0&7&6&5&4&11&10&9&8&15&14&13&12\\\hline 4&4&5&6&7&0&1&2&3&12&13&14&15&8&9&10&11\\\hline 5&5&4&7&6&1&0&3&2&13&12&15&14&9&8&11&10\\\hline 6&6&7&4&5&2&3&0&1&14&15&12&13&10&11&8&9\\\hline 7&7&6&5&4&3&2&1&0&15&14&13&12&11&10&9&8\\\hline 8&8&9&10&11&12&13&14&15&0&1&2&3&4&5&6&7\\\hline 9&9&8&11&10&13&12&15&14&1&0&3&2&5&4&7&6\\\hline 10&10&11&8&9&14&15&12&13&2&3&0&1&6&7&4&5\\\hline 11&11&10&9&8&15&14&13&12&3&2&1&0&7&6&5&4\\\hline 12&12&13&14&15&8&9&10&11&4&5&6&7&0&1&2&3\\\hline 13&13&12&15&14&9&8&11&10&5&4&7&6&1&0&3&2\\\hline 14&14&15&12&13&10&11&8&9&6&7&4&5&2&3&0&1\\\hline 15&15&14&13&12&11&10&9&8&7&6&5&4&3&2&1&0\\\hline \end{array} $$

稍微验证一下发现它确实符合交换律、结合律……等等这不就是异或吗？怎么证明呢？

还是先来考虑一下乘法吧。首先 $0\alpha=\alpha0=0$，那 $1\times1$ 就不能是 $0$ 了，那就 $1$ 吧。好，$1$ 就是幺元了！那么 $1\alpha=\alpha1=\alpha$。$2\times2$ 等于多少？可以是 $1$ 吗？这样的话 $(2+1)\times(2+1)=2\times2+1\times2+2\times1+1\times1=0$，似乎不太对。可以是 $2$ 吗？$1\times2$ 已经是 $2$ 了啊。那就 $3$？暂时看起来没什么问题。

等等我们发现了什么……$(x+y)^2=x^2+y^2$，因此两个数的平方不能相同！这个性质很优美诶。

因为 $3=1+2$，由分配律 $3$ 相关的都做完了。

$2\times 4$ 是多少？显然不能为 $2\times0=0,2\times1=2,2\times2=3,2\times3=1$。如果是 $4+x(0\le x<4)$ 的话，那 $2\times4=4+x$ 得 $(2+1)\times4=x$，$3\times4<4$ 的话也不行（因为 $3\times0=0,3\times1=3,3\times2=1,3\times3=2$）。那么就最小是 $2\times4=8$ 了。

$3\times4=2\times4+1\times4=8+4=12$。

那 $4\times 4$ 是多少？根据之前的结果，它不能等于 $0^2=0,1^2=1,2^2=3,3^2=3,1\times4=4$。能等于 $5$ 吗？这意味着 $4$ 是 $x^2+x+1=0$ 的根。可是这是 $(x+2)(x+3)=0$！而 $(4+2)\times(4+3)$ 不能为 $0$。因此 $5$ 也不行。那就 $6$ 吧。先看着……

好像导致 $a\times b=x$ 矛盾的点都是 $(a+a')(b+b')=0$？那就让这些全都不为 $0$ 即可。这启发我们定义

$$\alpha\beta=\operatorname{mex}\{\alpha\delta+\gamma\beta+\gamma\delta|\gamma<\alpha,\delta<\beta\} $$

据此列出表格

$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \times&0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15\\\hline 0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\\hline 1&0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15\\\hline 2&0&2&3&1&8&10&11&9&12&14&15&13&4&6&7&5\\\hline 3&0&3&1&2&12&15&13&14&4&7&5&6&8&11&9&10\\\hline 4&0&4&8&12&6&2&14&10&11&15&3&7&13&9&5&1\\\hline 5&0&5&10&15&2&7&8&13&3&6&9&12&1&4&11&14\\\hline 6&0&6&11&13&14&8&5&3&7&1&12&10&9&15&2&4\\\hline 7&0&7&9&14&10&13&3&4&15&8&6&1&5&2&12&11\\\hline 8&0&8&12&4&11&3&7&15&13&5&1&9&6&14&10&2\\\hline 9&0&9&14&7&15&6&1&8&5&12&11&2&10&3&4&13\\\hline 10&0&10&15&5&3&9&12&6&1&11&14&4&2&8&13&7\\\hline 11&0&11&13&6&7&12&10&1&9&2&4&15&14&5&3&8\\\hline 12&0&12&4&8&13&1&9&5&6&10&2&14&11&7&15&3\\\hline 13&0&13&6&11&9&4&15&2&14&3&8&5&7&10&1&12\\\hline 14&0&14&7&9&5&11&2&12&10&4&13&3&15&1&8&6\\\hline 15&0&15&5&10&1&14&4&11&2&13&7&8&3&12&6&9\\\hline \end{array} $$

稍微验证一下发现它确实符合交换律、分配律……而且似乎每 $[2^{2^N}]$ 以内对乘法封闭？而因为消去律一定有一个 $\beta$ 满足 $\alpha\beta=1$，所以就对四则运算封闭了……？怎么证明呢。

加减乘除

定义 . 对于任意序数 $\alpha,\beta$，我们递归定义它们的异或（Nim 和）为

$$\alpha+\beta=\operatorname{mex}(\{\alpha+\delta|\delta<\beta\}\cup\{\gamma+\beta|\gamma<\beta\}) $$

定义 . 对于任意序数 $\alpha,\beta$，我们递归定义它们的 Nim 积为

$$\alpha\beta=\operatorname{mex}\{\alpha\delta+\gamma\beta+\gamma\delta|\gamma<\alpha,\delta<\beta\} $$

我们记 $\alpha^*$ 为一变量，它能取值所有 $<\alpha$ 的序数和部分 $>\alpha$ 的序数。（即，其取值范围的 $\operatorname{mex}$ 为 $\alpha$）如果 $\alpha$ 的定义式/计算式为 $\operatorname{mex}(S)$，称 $S$ 的所有元素为 $\alpha$ 的排除项。

定理 . 对于任意序数 $\alpha,\beta,\gamma$，$\alpha+\beta=\alpha+\gamma$ 当且仅当 $\beta=\gamma$。

证明 . 充分性显然。必要性考虑反证。若 $\beta\neq \gamma$，不妨设 $\beta<\gamma$，则 $\alpha+\beta$ 为 $\alpha+\gamma$ 的一排除项，矛盾。

定理 .（加法的冗余定理）对于任意序数 $\alpha,\beta$，

$$\alpha+\beta=\operatorname{mex}(\{\alpha+\beta^*|\beta^*\}\cup\{\alpha^*+\beta|\alpha^*\}) $$

证明 . 显然 $\alpha+\beta$ 的所有排除项都被排除了，而其它的元素排除项含有 $\alpha+\beta$，故右侧取值为 $(\alpha+\beta)^*$，即 $\operatorname{mex}$ 为 $\alpha+\beta$。

定理 . 对于任意序数 $\alpha,\beta,\gamma$，有

1. $\alpha+0=\alpha$
2. $\alpha+\beta=\beta+\alpha$
3. $(\alpha+\beta)+\gamma=\alpha+(\beta+\gamma)$
4. $\alpha+\alpha=0$

证明 . 直接归纳即可。注意第三条要用到冗余定理。

推论 . （多个数的加法计算式）在证明第三条的归纳过程中，我们可以用归纳类似地证明：对于任何 $n$ 个序数 $\alpha_1,\alpha_2,\cdots,\alpha_n$，有：

$$\sum_{i=1}^n\alpha_i=\operatorname{mex}\bigcup\limits_{i=1}^n\{\sum_{j=1}^n\begin{cases}\alpha&j=i\\\alpha_j&j\neq i\end{cases}|\alpha<\alpha_j\} $$

定理 . 对于任意序数 $\alpha$，有 $\alpha0=0\alpha=0$。

证明. $\alpha0$ 和 $0\alpha$ 均无排除项，即证。

定理 . 对于任意序数 $\alpha,\beta,\gamma$，$\alpha\beta=\alpha\gamma$ 当且仅当 $\beta=\gamma$ 或 $\alpha=0$。

证明. 充分性显然。必要性考虑反证。若 $\beta\neq \gamma$，不妨设 $\beta<\gamma$，而 $0<\alpha$，故 $\alpha\gamma$ 的排除项有 $\alpha\beta+0\gamma+0\beta=\alpha\beta$，矛盾。

定理 .（乘法的冗余定理）对于任意序数 $\alpha,\beta$，有

$$\alpha\beta=\operatorname{mex}\{\alpha\beta^*+\alpha^*\beta+\alpha^*\beta^*|\alpha^*,\beta^*\} $$

证明 . 显然 $\alpha\beta$ 的排除项都被排除了。因此我们只需证 $\alpha\beta\neq \alpha\beta^*+\alpha^*\beta+\alpha^*\beta^*$ 即可。根据异或的自逆，这等价于 $\alpha\beta+\alpha\beta^*+\alpha^*\beta+\alpha^*\beta^*\neq 0$。显然，其它三者之和为最大的一者的排除项，即证。

定理 . 对于任意序数 $\alpha,\beta,\gamma$，有

1. $\alpha1=\alpha$
2. $\alpha\beta=\beta\alpha$
3. $(\alpha\beta)\gamma=\alpha(\beta\gamma)$
4. $\alpha(\beta+\gamma)=\alpha\beta+\alpha\gamma$

证明 . 直接归纳即可。注意第三条和第四条要用到冗余定理。

推论 .（多个数的乘法计算式）在证明第三条的归纳过程中，我们可以用归纳类似地证明：对于任何 $n$ 个序数 $\alpha_1,\alpha_2,\cdots,\alpha_n$，有：

$$\prod_{i=1}^n\alpha_i=\operatorname{mex}\{\sum_{I\subsetneq\{1,2,\cdots,n\}}\prod_{j=1}^n\begin{cases}\alpha_j&j\in I\\\beta_j&j\not\in I\end{cases}|\beta_j<\alpha_j\} $$

定义 . 对于任意序数 $\alpha>0$，定义

$$S=\{0\}\cup\{\gamma^{-1}(1+(\alpha+\gamma)\delta)|0<\gamma<\alpha,\delta\in S\} $$

则定义 $\alpha^{-1}=\operatorname{mex}(S)$。对于任意序数 $\alpha,\beta$，定义 $\alpha/\beta=\dfrac\alpha\beta=\alpha\beta^{-1}$。

（注：这个 $S$ 是一个递归的定义，即 $S$ 包含了上述操作在有限步以内能生成的所有数。）

定理 .

1. 对于任何序数 $\alpha>0$，设 $\beta$ 为 $\alpha^{-1}$ 的一排除项，则 $\alpha\beta\neq 1$。
2. 对于任何序数 $\alpha>0$，设 $\beta$ 为 $\alpha\alpha^{-1}$ 的一（冗余）排除项，$\beta\neq 1$。
3. 对于任何序数 $\alpha>0$，$\alpha\alpha^{-1}=1$。

证明 . 考虑归纳。

1. 若 $\beta=0$ 显然，否则设 $\beta=\gamma^{-1}(1+(\alpha+\gamma)\delta)$。则 $1+\alpha\beta=\gamma\gamma^{-1}+\alpha\beta=\gamma^{-1}(\alpha+\gamma+\alpha(\alpha+\gamma)\delta)=\gamma^{-1}(\alpha+\gamma)(1+\alpha\delta)$。显然 $\gamma^{-1}\neq 0$，又因 $\gamma<\alpha$ 有 $\alpha+\gamma$ 不为 $0$，根据归纳假设又有，$1+\alpha\delta$ 不为 $0$，故乘积不为 $0$，即证。
2. 设 $\beta=\gamma\alpha^{-1}+\alpha(\alpha^{-1})^*+\gamma(\alpha^{-1})^*$，其中 $(\alpha^{-1})^*$ 为 $\alpha^{-1}$ 的一排除项。若 $\gamma$ 等于 $0$，这就是前一条所证的。否则因为 $\lambda=\gamma^{-1}(1+(\alpha+\gamma)(\alpha^{-1})^*)$ 也为 $\alpha^{-1}$ 的一排除项，又因为 $\gamma\gamma^{-1}=1$，故 $\beta=1+\gamma(\alpha^{-1}+\lambda)\neq 1$。
3. 显然 $\alpha\alpha^{-1}\neq 0$，因为 $\alpha^{-1}\neq 0$。而由 2 得 $\alpha\alpha^{-1}$ 的排除项不含 $1$，即证。

扩张，扩张，扩张

定理 . 设 $\Delta$ 不对加法封闭，则 $\Delta=\alpha+\beta$，其中 $(\alpha,\beta)$ 为字典序最小的一对 $\Delta$ 的元素满足 $\alpha+\beta$ 不在 $\Delta$ 中。

证明 . 显然 $\alpha+\beta\ge \Delta$，但是 $\alpha+\beta$ 的排除项都在 $\Delta$ 中。（这是因为字典序更小了）即证。

定理 . 设 $\Delta$ 对加法封闭，则对于任意 $\alpha$ 和 $\beta\in \Delta$ 有 $[\Delta\alpha]+\beta=[\Delta\alpha+\beta]$。

（例. $4=\{0,1,2,3\}$ 对加法封闭，故 $8+3=[4\times2]+3=[4\times 2+3]=11$。）

证明 . 考虑归纳。左侧的排除项为：

• $[\Delta\alpha'+\gamma]+\beta$，其中 $\alpha'<\alpha,\gamma<\Delta$。这是因为带余除法。
• $[\Delta\alpha]+\delta$，其中 $\delta<\beta$。

根据归纳假设，左侧即为 $[\Delta\alpha']+(\beta+\gamma)$。而由于 $\Delta$ 形成一个群，$\beta+\gamma$ 恰好能取遍所有的 $\gamma'<\Delta$！故根据归纳假设，所有的排除项为 $[\Delta\alpha'+\gamma']$ 和 $[\Delta\alpha+\delta]$，这恰为所有小于 $[\Delta\alpha+\beta]$ 的数，即证。

定理 . 设 $\Delta$ 对加法封闭但不对乘法封闭，则 $\Delta=\alpha\beta$，其中 $(\alpha,\beta)$ 为字典序最小的一对 $\Delta$ 的元素满足 $\alpha\beta$ 不在 $\Delta$ 中。

（例. $8$ 对加法封闭但不对乘法封闭，字典序最小的 $(\alpha,\beta)=(2,4)$，故 $8=2\times4$。）

证明 . 显然 $\alpha\beta\ge \Delta$，但是 $\alpha\beta$ 的排除项都在 $\Delta$ 中。（这是因为字典序更小了，且加法封闭）即证。

定理 . 设 $\Delta$ 对加法和乘法封闭，对加法封闭的 $\Gamma\le \Delta$ 满足 $\Gamma$ 中的非零元都在 $\Delta$ 中有乘法逆元（即与其乘积为 $1$ 的元素），则对于任意 $\gamma\in \Gamma$，有 $\Delta\gamma=[\Delta\gamma]$。

（例. $4=\{0,1,2,3\}$ 对加法和乘法封闭，且 $4\le 4$ 中的所有非零元都在 $4$ 中有逆，故 $3\times 4=[3\times4]=12$。）

证明 . 考虑归纳。$\Delta\gamma$ 的排除项为 $\Delta\alpha+\beta\alpha+\beta\gamma,\beta<\Delta,\alpha<\gamma$。只需证对于任何 $\alpha<\gamma$，有 $\Delta\alpha+\beta(\alpha+\gamma)$ 能取遍所有 $[\Delta\alpha+\delta]=[\Delta\alpha]+\delta=\Delta\alpha+\delta$。取 $\beta=\delta(\alpha+\gamma)^{-1}$ 即可。

定理 . 设 $\Delta$ 为对四则运算封闭但有些多项式方程无解，设 $p(x)$ 为系数在 $\Delta$ 中，在 $\Delta$ 中没有根的字典序最小的多项式（从高次项到低次项依次比较）。则 $p(\Delta)=0$。对于任何次数比 $p$ 小的多项式 $p'(x)$，有 $p'(\Delta)=[p'(\Delta)]$。

（注意序数乘法可能没有交换律，若 $p(x)=\sum \alpha_ix^i$，这里 $[p'(\Delta)]=\sum \Delta^i\alpha_i$，$i$ 从大到小加。）

（例。 $4=\{0,1,2,3\}$ 对四则运算封闭，但是有无根多项式 $x^2+x+2=0$，故 $4^2=4+2=6$。）

（注：你问对加、乘封闭但没法做除法的情况去哪里了？事实上有，但是书中的证明有一定问题，而且我们用不到，就咕了。）

证明 . 设 $p$ 的次数为 $n$。对于任何一个 $N$，考虑 $\Delta^N$ 的排除项为：

$$\prod_{i=1}^N\alpha_i=\operatorname{mex}\{\sum_{i=0}^{N-1}\sum_{I\subsetneq\{1,2,\cdots,N\},|I|=i}\Delta^i\prod_{j\not\in I}\beta_j|\beta_j<\alpha_j\} $$

先归纳地证明若 $N<n$ 则 $N$ 次多项式 $p'(x)$ 有 $p'(\Delta)=[p'(\Delta)]$。

1. 先考虑 $\Delta^N$。只需证明它的排除项能取遍所有 $\sum\limits_{i=0}^{N-1}\Delta^i\gamma_i=[\sum\limits_{i=0}^{N-1}\Delta^i\gamma_i]$ 即可。考虑多项式 $q(x)=x^N+\sum\limits_{i=0}^{N-1} x^i\gamma_i$。因为 $<n$ 次多项式均有根，它一定可以因式分解为一次因式。设其根为 $\delta_1,\delta_2,\cdots,\delta_n$，重根算多次。根据 Vieta 定理，$\beta_j=\delta_j$ 即为所求。
2. 再考虑 $\Delta^N\delta$，其中 $\delta\in \Delta$。它的排除项为 $\{\Delta^N\gamma+q(\Delta)(\gamma+\delta)|\gamma<\delta,\deg q<N,[x^i]q(x)\in \Delta\}$。只需证明对于任何 $\gamma$，$q(\Delta)(\gamma+\delta)$ 能取遍每个 $q'(\Delta)$ 即可。因为 $\gamma+\delta\in \Delta$，故其有逆元，而根据归纳假设，次数更小的多项式乘 $\Delta$ 的元素正常乘即可，故取 $q(x)=q'(x)(\gamma+\delta)^{-1}$ 即可。
3. 再考虑 $p'(\Delta),\deg p'=N$。根据归纳假设，次数更小的多项式加法是正常算的，故 $\Delta^N$ 为一个群。因此设 $p'(x)=x^N\delta+q'(x)$，则 $p'(\Delta)=\Delta^N\delta+q'(\Delta)=[\Delta^N\delta]+[q'(\Delta)]=[\Delta^N\delta+q'(\Delta)]=[p'(\Delta)]$。

再证 $p(\Delta)=0$。设 $p(x)=x^n+q(x)$（显然，若最高次项系数不为 $1$，则系数均乘以其逆元字典序更小）。考虑 $\Delta^n$。和以上过程类似，比 $q(\Delta)$ 小（等价于字典序小）的均为 $\Delta^n$ 的排除项。但 $q(\Delta)$ 不是，否则根据 Vieta 定理 $p$ 就在 $\Delta$ 内有根了。因此 $\Delta^n=q(\Delta)$，即 $p(\Delta)=0$。

定理 . 设 $\Delta$ 对四则运算封闭，且所有多项式方程均有根。则对于任意多项式 $p(x)$ 有 $p(\Delta)=[p(\Delta)]$。

证明 . 和上述定理类似。

推论 . 设 $\Delta$ 对四则运算封闭，$\Delta$ 不是任何 $\Delta$ 上多项式方程的根。

加法

定理 . 若 $\Delta$ 对加法封闭，则下一个对加法封闭的序数为 $[\Delta2]$。

证明 . 显然 $\{x|x<\Delta\}$ 和 $\{\Delta+x|x<\Delta\}$ 两两不同，所以至少要包含它们。所以 $<[\Delta2]$ 的不对加法封闭。而因为 $[\Delta+x]=\Delta+x$，所以 $[\Delta2]$ 对加法封闭。

定理 . 每个序数 $\alpha$ 都可以写成 $[2^{\beta_0}+2^{\beta_1}+\cdots+2^{\beta_{n-1}}]$，其中 $n$ 有限，$\beta$ 严格递减。且 $\alpha=[2^{\beta_0}]+[2^{\beta_1}]+\cdots+[2^{\beta_{n-1}}]$。

（例如，$6=[2^2+2^1]=[2^2]+[2^1]=4+2$。）

（注：这也就说明了加法就是异或。）

证明 . 设 $\alpha>0$，则取最大的 $2^\beta\le \alpha$，设 $\alpha=[2^\beta+\gamma]$，显然 $\gamma<2^\beta$，故 $\alpha=[2^\beta]+\gamma$。归纳即可。

扩张（试试看！）

来试着通过扩张的几个定理来扩张，得到一些对四则运算封闭的序数吧！

首先最小的非平凡的肯定是 $2=\{0,1\}$。我们知道，接下来需要找到一个无解方程。显然一次方程就是除法，不可能无解。二次方程呢？对于有限的对四则运算封闭的 $n$，如果有一个无解的二次方程，那下一个就是对四则运算封闭的 $[n^2]=\{[an+b]|a<n,b<n\}=\{an+b|a<n,b<n\}$ 了。（记 $n$ 为 $\mathbb F_n$，这其实就是 $\mathbb F_n[x]/p(x)$，其中 $p(x)$ 为字典序最小的无根多项式）

定理 . 对于有限的 $n$，若 $n$ 对四则运算封闭，则对任意 $a<n$，存在 $b<n$，$b^2=a$。

证明 . 显然 $c\to c^2(c<n)$ 为单射，故为满射。

所以不需要考虑 $x^2$ 型的了。那 $x^2+x$ 呢？

定理 . 对于有限的 $n>1$，若 $n$ 对四则运算封闭，恰有半数 $a<n$，满足不存在 $b<n$，$b^2+b=a$。

证明 . 显然 $c^2+c=d^2+d$ 当且仅当 $(c+d)(c+d+1)=0$，即 $c=d$ 或 $c=d+1$，故恰有一半的 $c^2+c$ 能被取到。

因此有限情况的扩张都是 $x^2+x+a$，于是我们做完了……？等等扩张完还是封闭的吗？显然加、乘是封闭呢。除呢？（其实有更一般的关于扩张的证明，但是这里不必要）

定理 . 对于有限的 $n$，若 $n$ 对加法、乘法封闭，则 $n$ 对四则运算封闭。

证明 . 设 $c\neq 0$，则 $x\to cx(x<n)$ 为单射，故为满射，故存在 $cx=1$。

好，于是我们有：

定理 . 所有有限的对四则运算封闭的序数为：

$$2,4,16,\cdots,[2^{2^n}],\cdots$$

其中每一个是上一个的[平方]。

证明 . 刚才所讨论的就是这个。

推论 . 若 $k<[2^{2^n}]$，则 $2^{2^n}k=[2^{2^n}k]$。

等等，知道是域有什么用，到底怎么算啊？$2\to 4$ 的过程中，最小的无解方程为 $x^2+x+1$，故 $2^2=2+1=3$。$4\to 16$ 的过程中，最小的无解方程为 $x^2+x+2$，故 $4^2=4+2=6$。在 $16\to 256$ 的过程中呢？对于每个 $x<16$ 计算 $x^2+x$，发现恰好是 $0\sim 7$ 各一个……？因此 $16^2=16+8=24$。

更一般地，我们考虑证明：

定理 .

1. 对于任何非负整数 $n$，若 $x<[2^n]$，则 $x^2<[2^n]$。
2. 对于任何正整数 $x$，$x$ 与 $x^2$ 的最高位相同。换言之，若 $x<[2^{n+1}]$，则 $x^2+x<[2^n]$。
3. 对于任何非负整数 $n$，$\{x^2+x|x<[2^{2^n}]\}=[2^{2^n-1}]$
4. 对于任何非负整数 $n$，$[2^{2^n}]^2=[\dfrac32\times2^{2^n}]$。

证明 . 以下归纳不会出现循环论证交给读者作为练习。

1. 因为 $(x+y)^2=x^2+y^2$，且 $[2^n]$ 是一个群，因此只需证明 $x=[2^k]$ 的情况 $x^2<[2^{k+1}]$ 即可。设 $k=\sum [2^{a_i}]$，则 $x=\prod [2^{2^{a_i}}]$。（因为 $[2^{2^{a_i}}]$ 对四则运算封闭，所以乘法和直接乘没区别）因此 $x^2=\prod [2^{2^{a_i}}]^2$。依归纳假设，这即为 $x^2=\prod [2^{2^{a_i}}]+[2^{2^{a_i}-1}]$。按照乘法分配律展开后，每一项的[普通]积都不超过 $[2^{k}]$，因此 Nim 积也不超过 $[2^k]$（因为 Nim 积的排除项个数为普通积），即小于 $[2^{k+1}]$，故和小于 $[2^{k+1}]$。
2. 根据 1.，有 $y\to y^2$ 是 $[2^n]$ 到 $[2^n]$ 的双射，同时也是 $[2^{n+1}]$ 到 $[2^{n+1}]$ 的双射，因此是 $[2^{n+1}]\backslash [2^n]$ 到自身的双射，即证。自然推出后半句。
3. 之前证明过前者的大小刚好为 $[2^{2^n-1}]$，而取值范围也在 $[2^{2^n-1}]$ 内，即证。
4. 根据 3.，最小需要扩展的多项式为 $p(x)=x^2+x+[2^{2^n-1}]$，即 $[2^{2^n}]^2=[2^{2^n}]+[2^{2^n-1}]=[2^{2^n}+2^{2^n-1}]=[\dfrac 32\times2^{2^n}]$。

计算

那么问题来了，我们怎么对 Nim 数进行计算呢？

定理 . 假设位运算的时间复杂度为 $O(1)$，则存在 $O(1)$ 的算法，给定 $a,b<[2^{2^k}]$，计算 $a+b$。

证明 . 之前证明了 $a+b$ 是异或，调用即可。

定理 . 假设位运算的时间复杂度为 $O(1)$，则存在 $O(3^k)$ 的算法，给定 $k,a<[2^{2^k}]$，计算 $a[2^{2^k-1}]$。

证明 . $k=0$ 时可以 $O(1)$ 计算。若 $k\ge 1$，设 $\alpha=[2^{2^k-1}],B=[2^{2^{k-1}}],\beta=[2^{2^{k-1}-1}]$，则 $\alpha=B\beta$。设 $a=[Bp+q]=Bp+q$，则 $a\alpha=aB\beta=\beta B(Bp+q)=B^2\beta p+B\beta q=\beta p(B+\beta)+\beta qB={\color{red}(p+q)\beta}B+{\color{blue}p\beta\beta}$。递归计算 $L=(p+q)\beta,R_0=p\beta,R=R_0\beta$，则答案为 $LB+R=[LB+R]$。时间复杂度 $T(k)=3T(k-1)+O(1)=O(3^k)$。

定理 . 假设位运算的时间复杂度为 $O(1)$，则存在 $O(k3^k)$ 的算法，给定 $a,b<[2^{2^k}]$，计算 $ab$。

证明 . $k=0$ 时可以 $O(1)$ 计算。若 $k\ge 1$，设 $B=[2^{2^{k-1}}],\beta=[2^{2^{k-1}-1}]$。设 $a=pB+q,b=rB+s$，则 $ab=(pB+q)(rB+s)=prB^2+(ps+qr)B+qs=pr(B+\beta)+(ps+qr)B+qs=(pr+ps+qr)B+pr\beta+qs$。递归计算 $L_0=(p+q)(s+r),L_1=qs,L=L_0+L_1,R_0=pr,R_1={\color{red}R_0\beta},R=R_1+L_1$，则答案为 $LB+R=[LB+R]$。时间复杂度 $T(k)=3T(k-1)+O(3^k)=O(k3^k)$。

关于本题

我们还需要证明一个性质：

定理 . 对于对四则运算封闭的 $n=[2^{2^k}]$，任意 $x<n$ 有 $x^n=x$。

证明 . $x=0$ 时显然。否则 $y\to xy$ 是 $n$ 到本身的双射，且 $0$ 映射到 $0$。因此 $\prod\limits_{y=1}^{[n-1]}y=\prod\limits_{y=1}^{[n-1]}xy$，两边消去 $\prod\limits_{y=1}^{[n-1]}y$ 可得 $x^{[n-1]}=1$，即 $x^n=x$。

以上。