自动搬运

查看原文

来自洛谷，原作者为

	codecode 天堂有路我不走，学海无涯苦作舟

搬运于2025-08-24 22:17:19，当前版本为作者最后更新于2020-04-06 15:03:21，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

前言

upd(2021.02.13)：更改了所有已知错误与笔误；对一些评论有异议的地方增添了补充说明；更改了部分用词并修正了一些内容；修正了部分错误的 LaTeX。

另外，codecode 早已退役转战数竞，这次更新可能是对本博客的最后一次更新，但仍欢迎您反馈发现的问题/不懂的表述等说不定还会回来呢。

upd(2020.04.06)：更新了部分用词；修正了部分 LaTeX 错误；添加了部分内容。

---

楼下的大佬已经给出了正解，这里只是整理一下并帮他们补充完整证明。

作为数竞生，对于这种问题就想要给出一个完整的证明。（其实作为 OIer，只需要知道结论就可以了，不一定需要知道证明。（雾））

证明比较复杂，可能需要阅读并理解较长时间；如果不想看证明，可以跳到最后看结论。

证明过程

前置：费马定理，欧拉定理，拉格朗日定理。

这里只给出拉格朗日定理的证明。

前置 拉格朗日定理：设 $p$ 为素数，对于模 $p$ 意义下的整系数多项式

$$f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_0\;(p\nmid a_n) $$

的同余方程 $f(x)\equiv 0\pmod p$ 在模 $p$ 意义下至多有 $n$ 个不同解。

证明：对 $n$ 使用归纳法。当 $n=0$ 时，由于 $p\nmid a_0$，故 $f(x)\equiv 0\pmod p$ 无解，定理对 $n=0$ 的多项式 $f(x)$ 都成立。

若命题对于 $\deg f<n$ 的 $f$ 都成立，由反证法，假设存在一个满足题目条件的 $f$ 在模 $p$ 意义下有着至少 $n+1$ 个不同的解 $x_0,x_1,\cdots,x_{n}$。

可设 $f(x)-f(x_0)=(x-x_0)g(x)$，则 $g(x)$ 在模 $p$ 意义下是一个至多 $n-1$ 次的多项式。现在由 $x_0,x_1,\cdots,x_n$ 都是 $f(x)\equiv 0\pmod p$ 的解，知对 $1\leq i\leq n$，都有

$$(x_i-x_0)g(x_i)\equiv f(x_i)-f(x_0)\equiv 0\pmod p $$

而 $x_i \not\equiv x_0 \pmod p$，故 $g(x_i)\equiv 0\pmod p$，从而 $g(x)\equiv 0\pmod p$ 有至少 $n$ 个根，与归纳假设矛盾。

所以，命题对 $n$ 次多项式也成立，定理获证。

补充：关于拉格朗日定理的证明中，由于 $f(x_i)=0$，故 $f(x)-f(x_i)$ 就是 $f(x)$，不影响阅读。

---

下面来看看阶与原根。

阶：由欧拉定理可知，对 $a\in \mathbf{Z},m\in\mathbf{N}^{*}$，若 $\gcd(a,m)=1$，则

$$a^{\varphi(m)}\equiv 1\pmod m$$

因此满足同余式 $a^n \equiv 1 \pmod m$ 的最小正整数 $n$ 存在，这个 $n$ 称作 $a$ 模 $m$ 的阶，记作 $\delta_m(a)$。

原根：设 $m \in \mathbf{N}^{*}$，$a\in \mathbf{Z}$。若 $\gcd(a,m)=1$，且 $\delta_m(a)=\varphi(m)$，则称 $a$ 为模 $m$ 的原根。

关于阶有一个较为显然的性质：

若 $a^n \equiv 1 \pmod m$，则 $\delta_m(a)|n$。

证明： 对 $n$ 除以 $\delta_m(a)$ 作带余除法，设

$$n=\delta_m(a)q+r,0\leq r<\delta_m(a)$$

若 $r>0$，则

$$a^r\equiv a^r(a^{\delta_m(a)})^q\equiv a^n \equiv 1 \pmod m $$

这与 $\delta_m(a)$ 的最小性矛盾。故 $r=0$，即 $\delta_m(a)|n$。

应评论：这里区分出 $r>0$ 是为证明 $r=0$。

---

阶还有两个重要的性质。

性质 $1$：设 $m\in\mathbf{N}^{*}$，$a,b\in\mathbf{Z}$，$\gcd(a,m)=\gcd(b,m)=1$，则

$$\delta_m(ab)=\delta_m(a)\delta_m(b)$$

的充分必要条件是 $\gcd(\delta_m(a),\delta_m(b))=1$。

证明： 必要性。由 $a^{\delta_m(a)}\equiv 1 \pmod m$ 及 $b^{\delta_m(b)} \equiv 1 \pmod m$，可知

$$(ab)^{\operatorname{lcm}(\delta_m(a),\delta_m(b))}\equiv 1 \pmod m $$

由前面所述阶的性质，有

$$\delta_m(ab)|\operatorname{lcm}(\delta_m(a),\delta_m(b)) $$

又由于 $\delta_m(ab)=\delta_m(a)\delta_m(b)$，故

$$\delta_m(a)\delta_m(b)|\operatorname{lcm}(\delta_m(a),\delta_m(b)) $$

即 $\gcd(\delta_m(a),\delta_m(b))=1$。

充分性。由 $(ab)^{\delta_m(ab)}\equiv 1 \pmod m$ 可知

$$1 \equiv (ab)^{\delta_m(ab)\delta_m(b)}\equiv a^{\delta_m(ab)} \pmod m $$

故 $\delta_m(a)|\delta_m(ab)\delta_m(b)$。结合 $\gcd(\delta_m(a),\delta_m(b))=1$ 即得

$$\delta_m(a)|\delta_m(ab)$$

对称地，同理可得

$$\delta_m(b)|\delta_m(ab)$$

所以

$$\delta_m(a)\delta_m(b)|\delta_m(ab)$$

另一方面，有

$$(ab)^{\delta_m(a)\delta_m(b)}\equiv(a^{\delta_m(a)})^{\delta_m(b)}\times(b^{\delta_m(b)})^{\delta_m(a)}\equiv 1 \pmod m $$

故

$$\delta_m(ab)|\delta_m(a)\delta_m(b)$$

综合以上两点即得

$$\delta_m(ab)=\delta_m(a)\delta_m(b)$$

性质 $1$ 证毕。

性质 $2$：设 $k \in \mathbf{N}$，$m\in \mathbf{N}^{*}$，$a\in\mathbf{Z}$，$\gcd(a,m)=1$，则

$$\delta_m(a^k)=\dfrac{\delta_m(a)}{\gcd(\delta_m(a),k)} $$

证明：注意到

$$a^{k\delta_m(a^k)}=(a^k)^{\delta_m(a^k)}\equiv 1 \pmod m $$$$\Rightarrow \delta_m(a)|k\delta_m(a^k)$$ $$\Rightarrow \dfrac{\delta_m(a)}{\gcd(\delta_m(a),k)}|\delta_m(a^k) $$

另一方面，由 $a^{\delta_m(a)}\equiv 1 \pmod m$，可知

$$(a^k)^{\frac{\delta_m(a)}{\gcd(\delta_m(a),k)}}=(a^{\delta_m(a)})^{\frac{k}{\gcd(\delta_m(a),k)}}\equiv 1 \pmod m $$

故

$$\delta_m(a^k)|\dfrac{\delta_m(a)}{\gcd(\delta_m(a),k)} $$

综合以上两点，得

$$\delta_m(a^k)=\dfrac{\delta_m(a)}{\gcd(\delta_m(a),k)} $$

性质 $2$ 证毕。

---

回到正题，我们下面来证明，关于怎样的 $m$，其原根存在。

首先，$m=1,2,4$ 时，原根存在。

定理 $1$：对于奇素数 $p$，$p$ 有原根。

证明：先证一个引理：

引理：设 $a$ 与 $b$ 是与 $p$ 互素的两个整数，则存在 $c\in\mathbf{Z}$ 使得 $\delta_p(c)=\operatorname{lcm}(\delta_p(a),\delta_p(b))$。

该引理原来的证明存在错误，现已更改证明，感谢 @ lgLinZhengYu 及 @ Peanut_Tang 指出。

记 $r=\delta_p(a),t=\delta_p(b)$，设它们的“标准分解”（这里对指数只要求 $\max(\alpha_j,\beta_j)>0$）分别为

$$r=\prod_{j=1}^s p_j^{\alpha_j},\quad t=\prod_{j=1}^s p_j^{\beta_j} $$

令 $l$ 为所有使得 $\alpha_j\leq\beta_j$ 的 $p_j^{\alpha_j}$ 的乘积，令 $m$ 为所有使得 $\alpha_j>\beta_j$ 的 $p_j^{\alpha_j}$ 的乘积. 记 $r=lx,t=my$. 则这样定义的 $x,y$ 满足 $\gcd(x,y)=1$ 且 $\operatorname{lcm}(r,t)=xy$。

由性质 $2$，$\delta_p(a^l)=x,\delta_p(b^m)=y$，则由性质 $1$，$\delta_p(a^lb^m)=xy=\operatorname{lcm}(\delta_p(a),\delta_p(b))$，即取 $c=a^lb^m$ 即可。

回到原命题，对 $1 \sim (p-1)$ 依次两两使用引理，可知存在 $g\in \mathbf{Z}$ 使得

$$\delta_p(g)=\operatorname{lcm}\left(\delta_p(1),\delta_p(2),\cdots,\delta_p(p-1)\right) $$

这表明 $\delta_p(j)|\delta_p(g)\;,j=1,2,\cdots,p-1$，所以 $j=1,2,\cdots,p-1$ 都是同余方程

$$x^{\delta_p(g)}\equiv 1\pmod p$$

的根。由拉格朗日定理，可知方程的次数 $\delta_p(g) \geq p-1$。

又由费马小定理，易知 $\delta_p(g) \leq p-1$，故 $\delta_p(g)=p-1=\varphi(p)$。

综上可知 $g$ 为模 $p$ 的原根。

定理 $1$ 证毕。

---

定理 $2$：对于奇素数 $p$，$\alpha \in \mathbf{N}^{*}$，$p^\alpha$ 有原根。

证明：一个基本的想法是将模 $p$ 的原根平移。

先证明一个引理：

引理：存在模 $p$ 的原根 $g$，使得 $g^{p-1}\not\equiv 1 \pmod {p^2}$

引理的证明：事实上，任取模 $p$ 的原根 $g$，若 $g$ 不满足条件，我们认定 $g+p$ 满足条件。

易知 $g+p$ 也是模 $p$ 的原根。

我们有

$$\begin{aligned}(g+p)^{p-1}&\equiv C_{p-1}^0g^{p-1}+C_{p-1}^1pg^{p-2}\\&\equiv g^{p-1}+p(p-1)g^{p-2}\\&\equiv 1-pg^{p-2}\\&\not\equiv 1 \pmod {p^2}\end{aligned} $$

回到原题，我们证明若 $g$ 是一个满足引理条件的原根，则对任意 $\alpha\in\mathbf{N}^{*}$，$g$ 是模 $p^{\alpha}$ 的原根。

首先，证明下面的结论：对任意 $\beta\in\mathbf{N}^{*}$，都可设

$$g^{\varphi(p^\beta)}=1+p^{\beta}\times k_{\beta}$$

这里 $p\nmid k_{\beta}$。事实上，$\beta=1$ 时，由 $g$ 的选取可知结论成立。现设上式对 $\beta$ 时成立，则

$$\begin{aligned}g^{\varphi(p^{\beta+1})}&=(g^{\varphi(p^{\beta})})^{p}\\&=(1+p^{\beta}\times k_{\beta})^p\\&\equiv 1+p^{\beta+1}\times k_{\beta} \pmod {p^{\beta+2}}\end{aligned} $$

结合 $p\nmid k_{\beta}$ 可知命题对 $\beta+1$ 成立。

所以命题对任意 $\beta\in\mathbf{N}^{*}$ 都成立。

其次，记 $\delta=\delta_{p^\alpha}(g)$，则由欧拉定理，可知 $\delta|p^{\alpha-1}(p-1)$。

而由 $g$ 为模 $p$ 的原根，及 $g^{\delta}\equiv 1\pmod {p^\alpha}$ 可知 $(p-1)|\delta$。

所以可设 $\delta=p^{\beta-1}(p-1)$，这里 $1\leq \beta\leq \alpha$。

现在利用之前的结论，可知

$$g^{\varphi(p^{\beta})}\not\equiv 1\pmod {p^{\beta+1}}\Rightarrow g^{\delta}\not\equiv 1\pmod {p^{\beta+1}} $$

结合 $g^{\delta}\equiv 1\pmod {p^\alpha}$ 可知 $\beta \geq \alpha$。

综上可知，$\beta=\alpha$，即

$$\delta_{p^{\alpha}}(g)=p^{\alpha-1}(p-1)=\varphi(p^\alpha) $$

从而，$g$ 是模 $p$ 的原根。

定理 $2$ 证毕。

---

定理 $3$：对于奇素数 $p$，$\alpha\in\mathbf{N}^{*}$，$2p^{\alpha}$ 的原根存在。

证明：设 $g$ 是模 $p^{\alpha}$ 的原根，则 $g+p^{\alpha}$ 也是模 $p^{\alpha}$ 的原根。

在 $g$ 和 $g+p^{\alpha}$ 中有一个是奇数，设这个奇数是 $G$，则 $\gcd(G,2p^{\alpha})=1$。

由欧拉定理，$\delta_{2p^{\alpha}}(G)|\varphi(2p^{\alpha})$。

而 $G^{\delta_{2p^{\alpha}}(G)}\equiv 1\pmod {2p^{\alpha}}$，故

$$G^{\delta_{2p^{\alpha}}(G)}\equiv 1 \pmod {p^{\alpha}} $$

利用 $G$ 为模 $p^{\alpha}$ 的原根可知 $\varphi(p^{\alpha})|\delta_{2p^{\alpha}}(G)$。

结合 $\varphi(p^{\alpha})=\varphi(2p^{\alpha})$ 可知 $G$ 为模 $2p^{\alpha}$ 的原根。

定理 $3$ 证毕。

---

定理 $4$：对于 $m\notin\{1,2,4\}$，且不存在奇素数 $p$ 及 $\alpha \in \mathbf{N}^{*}$ 使得 $m\in\{p^{\alpha},2p^{\alpha}\}$，则对任意 $a\in\mathbf{Z}$，$\gcd(a,m)=1$，都有 $\delta_m(a)<\varphi(m)$，即模 $m$ 的原根不存在。

证明：对于 $m=2^{\alpha}$，$\alpha\in\mathbf{N}^{*},\alpha\geq 3$，则对任意奇数 $a=2k+1$ 均有

$$\begin{aligned}a^{2^{\alpha-2}}&=(2k+1)^{2^{\alpha-2}}\\&\equiv 1+C_{2^{\alpha-2}}^1(2k)+C_{2^{\alpha-2}}^{2}(2k)^{2}\\&\equiv1+2^{\alpha-1}k+2^{\alpha-1}(2^{\alpha-2}-1)k^2\\&\equiv 1+2^{\alpha-1}(k+(2^{\alpha-2}-1)k)\\&\equiv 1 \pmod {2^{\alpha}}\end{aligned} $$

其中最后一步用到 $k$ 与 $(2^{\alpha-2}-1)k$ 同奇偶，故其和为偶数。

若 $m$ 不是 $2$ 的幂，且 $m$ 为符合题目条件的数，则可设 $m=rt$，这里 $2<r<t$ 且 $\gcd(r,t)=1$。

此时，若 $\gcd(a,m)=1$，由欧拉定理可知

$$a^{\varphi(r)}\equiv 1 \pmod r\;,\quad a^{\varphi(t)}\equiv1\pmod t $$

注意到 $n>2$ 时，$\varphi(n)$ 为偶数，所以

$$a^{\frac{1}{2}\varphi(r)\varphi(t)}\equiv 1\pmod {rt} $$

进而

$$\delta_m(a)\leq\dfrac{1}{2}\varphi(r)\varphi(t)=\dfrac{1}{2}\varphi(rt)=\dfrac{1}{2}\varphi(m)<\varphi(m) $$

定理 $4$ 得证。

---

结论

上面的定理 $1$ 到 $4$ 完整的给出了原根的充要条件。截至目前，我们证明了仅有 $1,2,4$ 或奇素数 $p^{\alpha}$ 及 $2p^{\alpha}$ 有原根，其它的数都没有原根。

那么我们可以先预处理素数及其幂次，及其幂次的 $2$ 倍，$\Theta(1)$ 的判断一个数有没有原根。

如果一个数有原根，可以先求出最小正原根。

王元于 1959 年证明了若 $m$ 有原根，其最小原根是不多于 $m^{0.25}$ 级别的。

事实上，由大量试验数据可以发现，对于足够大的 $m$，其最小正原根的大小不是多项式级别的。

——百度百科

可以感性理解一下，模 $m$ 的原根有 $\varphi(\varphi(m))$ 个，密度很大，所以最小原根很小。

根据这个结论，我们可以从小到大枚举。由原根的定义，若 $g$ 为模 $m$ 的原根，则对于 $\varphi(m)$ 的任意素因数 $p$，必有

$$g^{\varphi(m)/p}\not\equiv 1 \pmod m$$

同时，满足如上条件的 $g$，必将是原根。

我们可以预处理出 $\varphi(m)$ 的所有素因数，快速幂来判断。

假如找到了一个原根 $g$，不难证明对于所有 $\gcd(x,\varphi(m))=1$ 的 $x$，$g^x$ 均为原根，所以模 $m$ 的原根有 $\varphi(\varphi(m))$ 个。

所以我们可以在找到 $g$ 后再枚举找出所有 $m$ 的原根，排序后按要求输出。

复杂度不会算

注意需要开 longlong。