同余代数

Alex_Wei · 2025-01-28 10:11:29 · 算法·理论

Luogu & cnblogs

数论中的同余代数和数论函数是数论在 OI 中的主要应用，本篇笔记总结了同余代数相关知识点。

尽管近年来的重大考试当中少有涉及同余代数的题目，但熟练掌握相关的各种算法和它们的推导过程对我们的思维水平有很大的锻炼。

数论和抽象代数的联系是非常密切的，以至于同余代数几乎完全属于抽象代数的范畴。如果能够从抽象代数（尤其是循环群）的角度自顶向下地学习同余代数（在 OI 中），那么它将非常简单且容易理解。例如：

• 循环群在同余代数中的最直接应用就是模 p 下的加法（见 1.10 小节）。
• 中国剩余定理的另一种形式 \mathbb Z / n\mathbb Z \cong \mathbb Z / n_1\mathbb Z \times \mathbb Z / n_2\mathbb Z \times \cdots \times \mathbb Z / n_k\mathbb Z（见 3.3 小节）。
• 考察 (\mathbb Z / n\mathbb Z) ^ \times 的结构性质给出了原根的存在性定理和在模意义下开 N 次根的算法（见 6.3 小节）。

打星号的小节（不含例题）需要一些抽象代数的前置知识，见 OI 的群论部分或抽象代数课程笔记。链接附在了参考资料部分。

定义与记号

Abstractness is the price of generality.

为了更好地理解同余理论相关算法，读者需熟知基本概念，如素数的定义，算数基本定理，同余符号及其含义，最大公约数等，并掌握基本算法如快速幂，辗转相除法求最大公约数（Euclid 算法）等。

说明

在模 1 下讨论整数同余毫无意义，下文所有同余式的模数默认 p > 1，有 a \cdot 1 \equiv a\pmod p。

定义

• 整除：若非零整数 a 是整数 b 的因数，则称 a 整除 b 或 b 被 a 整除，记作 a\mid b。如 2 \mid 4，822 \nmid 1064。
• 同余：若整数 a, b 模正整数 p 的余数相等，则称 a, b 在模 p 下同余，记作 a\equiv b\pmod p。如 15 \equiv 57 \pmod {7}，-1\equiv 7\pmod 8。
• 最大公约数：整数 a 和 b 的 最大公约数 为最大的整数 d 满足 d 整除 a 和 b，记作 \gcd(a, b)。如 \gcd(4, 6) = 2，\gcd(0, n) = n。
• 互质：若整数 a, b 满足 \gcd(a, b) = 1，则称 a, b 互质，记作 a\perp b。一般 a, b 均为非负整数。如 3\perp 8，1\perp n，4 \not \perp 6。
• 剩余类：模 p 同余的所有数构成的等价类被称为模 p 的 剩余类。模 p 下它们等价。
• 完全剩余系：\{0, 1, \cdots, p - 1\} 构成模 p 的 完全剩余系，记为 Z_p。
• 简化剩余系：所有小于 n 且与 n 互质的正整数构成模 n 的 简化剩余系，又称 既约剩余系 或 缩系，记为 (\mathbb {Z}/n\mathbb Z) ^ *。这个集合的大小为 \varphi(n)。

注意区分因数和因子：因数表示一个数的约数，因子表示乘积的一项。

记号

• 素数集：记 \mathbb P 表示素数集。\mathbb P = \{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, \cdots\}。
• 质因数次数：n 所含质因数 p 的次数记作 \nu_p(n)。p ^ {\nu_p(n)} \mid n 且 p ^ {\nu_p(n) + 1} \nmid n。
• 各位数字和：n 在 p 进制下的各位数字之和记作 s_p(n)。

基本知识（非常重要）

• 给定 a, b，使得 a\mid bx 的最小的 x 为 \frac {a} {\gcd(a, b)}，且所有这样的 x 恰为 \frac {a} {\gcd(a, b)} 的倍数。对每个质因数单独分析即得。特别地，若 bx\equiv 0 \pmod a 且 a\perp b，则 x\equiv 0 \pmod a。
• 对 d\mid m，在 1\sim m 中使得 \gcd(m, x) = d 的 x 的个数等于在 1\sim \frac m d 中使得 \frac m d \perp x 的 x 的个数，即 \varphi(\frac m d)。因为 \gcd(m, x) = d 等价于 \gcd(\frac m d, \frac x d) = 1。

1. 基础知识

OI 中的同余理论主要是 在模意义下解方程。

1.1 同余的性质

了解同余的性质是学习同余数论的基础。同余符号的根本含义：a \equiv b \pmod p 等价于 a = b + kp\ (k\in \mathbb Z)，前者是后者的简要写法。

在同余式中，加法和乘法的交换律与结合律以及乘法分配律依然成立。以下两条性质是进行模意义下计算的依据。

• 两整数相加（减）再对 p 取模等于两个数先对 p 取模再相加（减），再对 p 取模。
• 两整数相乘再对 p 取模等于两个数先对 p 取模再相乘，再对 p 取模。

证明

设 a = q_1p + r_1，b = q_2p + r_2，其中所有数都是整数且 0 \leq r_1, r_2 < n，即 r_1 = a\bmod p，r_2 = \bmod p。因为 kp\bmod p = 0，所以

(a + b)\bmod p = (q_1p + r_1 + q_2p + r_2)\bmod p = ((a\bmod p) + (b\bmod p)) \bmod p

乘法同理。\square

和等式一样，同余式的基本性质：若 a \equiv b \pmod p，则 a + c \equiv b + c \pmod p，ac\equiv bc\pmod p。

需要注意，即使 ac\equiv bc \pmod p，也不一定有 a\equiv b\pmod p。c\perp p 是命题成立（c 有乘法逆元）的充要条件。关于同余式的除法，见 1.3 小节。

1.2 Fermat 小定理

要求模数 p 为质数。

引理

当 p 是质数时，其因数只有 1 和 p。因此，若两个数相乘是 p 的倍数，则其中至少有一个是 p 的倍数。

这个引理很重要。

当 a 不是 p 的倍数时，不存在 x \neq y 且 1 \leq x, y < p 满足 xa \equiv ya\pmod p，否则 x - y 是 p 的倍数，与 1\leq x, y< p 的限制矛盾。

考虑 1\sim p - 1 所有数，它们乘以 a 之后在模 p 下互不相同且不为 0，所以仍得 1\sim p - 1 所有数。于是

因为 \prod_{i = 1} ^ {p - 1} i 不是 p 的倍数，所以

该结论称为 Fermat 小定理。根据推导过程，它适用于 p 是质数且 a 不是 p 的倍数的情形。

1.3 乘法逆元

定义

为了支持同余式的除法运算，需要引入乘法逆元的概念：对整数 a，若 ax \equiv 1 \pmod p，则称 x 为 a 在模 p 下的 乘法逆元，记作 (a ^ {-1})_p。模 p 同余式中出现乘法逆元，除非在符号的右下角标记模数，否则认为逆元在模 p 下，可直接写 a ^ {-1}。

乘法逆元不一定存在，也不一定唯一。在实际运算中，只需要任意一个。

考虑同余式 ax\equiv b\pmod p，若希望将同余式两侧同时除以 a，则只需乘以 a 的乘法逆元：

求法

根据 Fermat 小定理，当 p 为质数时，a\cdot a ^ {p - 2} \equiv 1 \pmod p，即

据此快速幂求出一个数在模质数下的乘法逆元。

当 p 不是质数时，a 存在乘法逆元当且仅当 a \perp p。我们将在第二章展开讨论。

以下给出几个模 质数 p 下求乘法逆元的常见技巧。

前缀逆元

增量法，设 1\sim i - 1 的逆元已知。

设 p = ki + r\ (0\leq r < i)，即 k 和 r 分别是 p 对 i 做带余除法的商和余数。ki + r \equiv 0 \pmod p，两边同时除以 ir，得

时间复杂度线性。模板题。

离线 \mathcal{O}(1) 逆元

求任意 n 个数 a_i\ (1 \leq a_i < p) 的逆元。

设 s 为 a 的前缀积。通过 Fermat 小定理算出 s_n ^ {-1} 后，计算 s_i ^ {-1} \equiv s_{i + 1} ^ {-1} \times a_{i + 1} 得到前缀积的逆元，则 a_i ^ {-1} \equiv s_{i - 1}\times s_i ^ {-1}。

时间复杂度 \mathcal{O}(n+\log p)。模板题。

在线 \mathcal{O}(1) 逆元

首先 \mathcal{O}(k) 预处理一段前缀 [1, k] 的逆元。对询问的 x，找到 u 使得 xu \bmod p \leq k，则 x ^ {-1} = u(xu \bmod p) ^ {-1}。

不能对每个 x 都预处理对应的 u，所以我们只能对一些 x 预处理。考虑将 1\sim p - 1 分成若干组，每组的 u 可共用或根据组代表元的 u 快速计算。

最简单的分组方式是整除。设阈值 B，x = qB + r，则 xu \equiv qBu + ru\pmod p，考虑让 ru 较小且 qBu\bmod p 较小。设 u 的阈值为 B_u，则 ru < BB_u。令 qBu\bmod p 和 ru 差不多，则时间复杂度至少为 \Omega(BB_u + \frac {p} B)。取 B = B_u = p ^ {\frac 1 3} 较优秀。

目标：对每个 q 求出 0 < u \leq p ^ {\frac 1 3} 使得 qBu\bmod p = v，满足 |v| \leq p ^ {\frac 2 3}。抽屉原理保证解存在：对 qBu_1 - v_1 \equiv qBu_2 - v_2\pmod p，(u_1 - u_2, v_1 - v_2) 即一组解。

枚举每个 u，考虑 q 从 0 增加到 \frac p B，每次增加 1 则 v 增加 Bu\leq p ^ {\frac 2 3}。若当前 q 对应的 v 不合法，因为合法 v 的区间长度大于 p ^ {\frac 2 3}，所以可立即找到下个合法 q。

对每个 u，共跳过 \mathcal{O}(\frac {p ^ {\frac 2 3} B u} {p}) 次（qBu 的最大值除以 p），每次跳过带来 \mathcal{O}(\frac {p ^ {\frac 2 3}} {Bu}) 个合法 q（合法区间长度除以步长），共有 \mathcal{O}(p ^ {\frac 1 3}) 个合法的 q。

复杂度 \mathcal{O}(n + p ^ {\frac 2 3})。模板题。

1.4 Lagrange 定理

我们知道代数学基本定理：n 次多项式在复数域 \mathbb C 上有且仅有 n 个可重根。那么，模意义下的多项式是否仍然满足该性质呢？

Lagrange 定理：对于 \mathbb Z_p\ (p\in\mathbb P) 上的整系数多项式 f(x) = \sum_{i = 0} ^ n a_i x ^ i，其中 p\nmid a_n，则 f(x)\equiv 0\pmod p 在模 p 下 至多 有 n 个不同解。

证明

考虑数学归纳法。当 n = 0 时定理成立，因为 a_0 \equiv 0\pmod p 无解（注意 p\nmid a_0）。

当 n > 0 时，假设方程有 n + 1 个不同解 x_0, x_1, \cdots, x_n。因为 f(x_0) \equiv 0\pmod p，所以 f(x) \equiv (x - x_0)g(x) \pmod p，其中 g(x) 是不超过 n - 1 次的多项式。

因为 x_i \neq x_0\ (1\leq i \leq n) 且 (x_i - x_0)g(x_i) \equiv 0\pmod p，故 x_1, x_2, \cdots, x_n 均为 g(x) 的根，矛盾。\square

解的数量并非恰为 n，而是不超过 n，例如 x ^ 2 - 2\equiv 0\pmod 3 无解，这是 Lagrange 定理和代数学基本定理的区别之一。所以 f(x) 在模 p 下并不一定可以被分解为 n 个一次式的乘积。

• 注意：p 不是质数时结论不成立，如 x ^ 2 \equiv 1\pmod 8 有解 x = 1,3, 5, 7。

1.5 Wilson 定理

一般形式

乘法逆元是相互的。若 a 是 x 的乘法逆元，则 x 也是 a 的乘法逆元。这启发我们思考：当 p 是质数时，1\sim p - 1 所有数能否两两配对互为逆元？

对 p\in\mathbb P 且 p > 2，考虑 x ^ 2 \equiv 1\pmod p 有解 x = \pm 1（Lagrange 定理保证不会有其它解存在），于是 2\sim p - 2 两两配对互为逆元，即 \prod_{i = 2} ^ {p - 2} i \equiv 1\pmod p。因此 (p - 1)!\equiv 1 \cdot (p - 1) \equiv -1\pmod p。对 p = 2 成立。

考虑 p 不是质数的情况：

• 当 p = q ^ 2 时，考虑 q 和 2q。它们相乘后模 p 等于 0。因此，若 2q < p，即 p 为大于 4 的完全平方数时，(p - 1)!\equiv 0\pmod p；
• 当 p = 4 时，3! \equiv 2\pmod 4；
• 当 p 为大于 4 的非完全平方数时，令 q 为 p 的最小质因数，则 q \neq \frac p q，所以 (p - 1)!\equiv 0\pmod p.

综上，我们得到 Wilson 定理：(p - 1)!\equiv -1\pmod p 当且仅当 p 是质数。

扩展形式

尝试将 Wilson 定理扩展至素数幂的情形。

考虑 p ^ k 以内所有与 p 互质的数的乘积模 p ^ k，记为 (p ^ k!)_p。

仍然考虑求解 x ^ 2 \equiv 1\pmod {p ^ k}，求出所有逆元为本身的数，并将不为 x 的其它所有数与其逆元两两配对。因为我们只考虑与 p 互质的数，所以逆元存在。因此只需考虑所有 x 的乘积。

因式分解得 (x + 1)(x - 1)\equiv 0\pmod {p ^ k}。

当 p > 2 时，x + 1 和 x - 1 不可能均是 p 的倍数，必然有 x + 1\equiv 0\pmod {p ^ k} 或 x - 1\equiv 0\pmod {p ^ k}。故仍有 (p ^ k!)_p\equiv -1\pmod {p ^ k}。

当 p = 2 时，有平凡解 \pm 1。除此以外，x + 1 和 x - 1 可能同时为 2 的倍数。但它们不可能同时为 4 的倍数。若 x + 1 和 x - 1 同时为 2 的倍数，那么将 (x + 1)(x - 1)\equiv 0\pmod {2 ^ k} 两侧除掉不能被 4 整除的数（模数除以 2，因为被除掉的数恰好贡献一个质因数 2），得到 x \pm 1\equiv 0\pmod {2 ^ {k - 1}}。当 p = 2 时，方程有四个解 \pm 1 和 2 ^ {k - 1}\pm 1。

注意 k = 1 时四个解均重合，此时 1!\equiv -1\pmod 2。k = 2 时两对解重合，此时 1\times 3\equiv -1\pmod 4。否则 1\times (-1) \times (2 ^ {k - 1} + 1) \times (2 ^ {k - 1} - 1)\equiv 1\pmod {2 ^ k}。

综上，得到 Wilson 定理的扩展形式

在 exLucas 中用到了该结论。

1.6 Kummer 定理

阶乘的素数幂次

给定正整数 n 和质数 p，求 \nu_p(n!)。

提出 1\sim n 当中所有 p 的倍数，将它们全部除以 p。这一步消掉的质因数个数为 \lfloor \frac n p \rfloor。上一步操作后，得到 1 \sim \lfloor \frac n p \rfloor。将所有 p 的倍数提出来，然后全部除以 p。这一步消掉的质因数个数为 \lfloor \frac n {p ^ 2} \rfloor。以此类推，直到 \lfloor \frac n {p ^ k} \rfloor < p。此时已经没有 p 的倍数了。有如下结论：

该结论由 Legendre 在 1808 年提出。

考虑换一种方法求和。尝试对 n 在 p 进制下的每一位，求出它对每次提出因数个数的贡献之和。令 c = \lfloor \log_p n \rfloor，设 n = \sum_{i = 0} ^ c a_i p ^ i\ (0\leq a_i < p)，则

其中用到了等比数列求和公式 \sum_{i = 0} ^ k p ^ i = \frac {p ^ k - 1}{p - 1}。

通过上述推导，得到 \nu_p(n!) 的另一种表示方法：n 减去 n 在 p 进制下的各位数字和，再除以 p - 1。特别地，当 p = 2 时，\nu_2(n!) = n - \mathrm{popcount}(n)。

组合数的素数幂次

根据组合数公式 \binom n m = \frac {n!} {m!(n - m)!}，有

考虑 n - m 和 m 在 p 进制下相加得到 n 的过程。每产生一次进位，各位数字之和就会减少 p - 1，因此 p 在 \binom n m 中的幂次等于 p 进制下 n - m 加 m 需要进位的次数。

该结论称为 Kummer 定理。

1.7 步长与子环

结论

在长为 n 的环上每一步走 k 条边，形成 d = \gcd(n, k) 个子环，每个环的环长为 \frac n {d}。

按顺序给环上的每个点标号 0, 1, 2, \cdots, n - 1。从 r 开始每一步走 k 条边，经过的点的编号与 r 在模 d 下同余，因为 n, k 均为 d 的倍数，r 加上 k 对 n 取模不改变 r\bmod d。

引理

当 n \perp k 时，从环上任意一点出发，能够走遍所有点。

证明

即证 (r + ck)\bmod n 对 0 \leq c < n 互不相同。假设存在 0 \leq i < j < n 有 r + ik\equiv r + jk\pmod n，移项得 (j - i)k \equiv 0\pmod n。因为 k\perp n，所以 n \mid j - i，这与 0\leq i, j < n 矛盾。\square

说明

这个引理本质上和最开始的基本知识等价。如果跳 x 步回到原来的位置，那么 n\mid kx，推出 x 是 \frac {n} {\gcd(n, k)} 的倍数。但 n\perp k，所以 x 无论如何都是 n 的倍数。

即当 k\perp n 时，ck \bmod n 取遍 0\sim n - 1，这是 Fermat 小定理的引理的推广，可以进一步推出 Euler 定理。

不妨设 0\leq r < d。考虑 0\sim n - 1 当中所有模 d 余 r 的数 r, r + d, \cdots, r + (\frac n d - 1)d，将它们重标号为 0, 1, \cdots, \frac n d - 1，形成长为 \frac n d 的子环。

因为 d 是 n, k 的最大公约数，所以 \frac n d\perp \frac k d。根据引理，在这个长为 \frac n d 的子环上每一步走 \frac k d 条边（相当于在原环上走 k 条边），能够走遍子环上的每一个点。

于是子环长为 \frac n d 即 \frac n {\gcd(n, k)}。每个模 d 的剩余系形成一个长为 \frac n d 的子环，子环个数为 d = \gcd(n, k)。

例题：P5582，P5887，P6187。

1.8 Euler 定理

前置知识：Euler 函数（见数论 II）。

一般形式

回顾 Fermat 小定理的证明过程，我们发现 p 是质数的条件只是为了保证 ax\bmod p 互不相同。由 1.7 小节的引理，这个条件可以仅由 a\perp p 保证。同时我们知道，两个模 p 互质的数相乘后模 p 仍与 p 互质。因此，我们尝试将费马小定理扩展至更一般的情况。

设 K_p 为 p 的简化剩余系。对于任意 x, y\in K_p，若 x \neq y，则 ax 和 ay 模 p 的余数不相等且仍与 p 互质。因此，在模 p 下，K_p 中的每个数乘以 a 后仍与 K_p 相等。故 \prod_{x\in K_p} x \equiv \prod_{x\in K_p} ax \pmod p。

等式两边同时除以 \prod_{x\in K_p} x 得到 Euler 定理

在计算与模数互质的某个数的幂时，指数可以对模数的 Euler 函数取模。可以用来化简公式或减小常数，前提是模数是定值或其 Euler 函数容易计算。

当 p 是质数时，\varphi(p) = p - 1，与 Fermat 小定理一致。

扩展形式

当 \gcd(a, p)\neq 1 时，不断乘以 a 会让 a ^ i 和 p 的 gcd 不断增加，直到某个特定的 a ^ r 之后 gcd 不再变化，因为此时 \gcd(a ^ r, p) 的每个质因数受到的限制都是 p 提供的。将 gcd 除掉之后得到 Euler 定理的条件，于是有 exEuler 定理

证明

设 d = \gcd(a ^ r, p)。在模 p 下考虑 a ^ r, a ^ {r + 1}, \cdots，它们均为 d 的倍数。因为 a\perp \frac p d，所以它们除以 d 之后会取遍所有与 \frac p d 互质的数。根据 Euler 定理，a ^ k \bmod {\frac p d} 有循环节 \varphi (\frac p d)，因此 (a ^ {r + k} \bmod {\frac p d})\times d 即 a ^ {r + k} \bmod p 也有长度为 \varphi (\frac p d) 的循环节。而 \varphi(\frac p d) \mid \varphi(p)，所以从 a ^ r 开始，对 k\geq 0，a ^ {r + k} \bmod p 有长度为 \varphi(p) 的循环节。

还需证明 r\leq \varphi(p)。感性理解就是如果 gcd 变化，一定会乘上一个因子，所以 r 是 \mathcal{O}(\log p) 级别的，会比 \varphi(p) 小。具体怎么证明呢？我们发现 r 就是 a 的每个质因数幂次 q_i ^ {k_i} 对应的 r_i 的最大值，所以只需对 a 是质数幂次 q ^ k 的情况证明。设 p 含 c 个质因数 q，则 r = \lceil\frac c k\rceil。因此，显然地，我们只需对 a 是质数 q 的情况证明，因为此时 r 最大。

设 p = q ^ cp'，则 r = c。由 Euler 函数的性质，\varphi(p) \geq \varphi(q ^ c) = q ^ {c - 1}(q - 1) \geq c。\square

1.9 同余式的除法

对于 a\equiv b\pmod p，一种除法是将 a, b 同时除以 d = \gcd(a, p) 以化简同余式（如果 b 无法除尽，则同余式不可能成立），此时 p 也应当除以 \gcd(a, p)。另一种除法是在 a\perp p 时，将同余式两侧同时除以 a，通过乘以 a 的乘法逆元实现，此时 p 保持不变。

读者需要区分这两种对同余式的基本变形方法。同余式的本质为存在 k 使得 a + kp = b，第一种除法相当于将等式两侧同时除以 d 得到 \frac a d + k\frac p d = \frac b d，因为等式左侧是整数，所以右侧也必须是整数，即 d\mid b。第二种除法相当于 ax + kpx = bx，其中 ax\equiv 1 \pmod p，于是存在 k' 使得 1 + k'p = bx\bmod p，即 1\equiv bx \pmod p，这是对同余式的简单变形。

*1.10 循环群和直积

循环群 是只由一个元素生成的群 G = \langle x\rangle = \{x ^ n\mid n\in \mathbb Z\}。大小相同的有限循环群是同构的。大小为 p 的循环群（p 阶循环群）记为 Z_p，则 x ^ p = 1（这里的 1 是单位元）。

对 Z_p 的直观理解是一个 p 个点的环 0\to 1\to \cdots \to p - 1\to 0，编号为 i 的点对应群内的元素 x ^ i，于是元素之间的乘法运算（定义一个群时的二元运算通常看成元素之间的乘法运算，但注意这并不是整数乘法，尽管它们的运算规则几乎一致）可以看成在环上移动。乘以 x ^ i 相当于在环上跳 i 步。为什么要想象成一个环呢？因为这样就可以用 1.7 小节的结论得到一些不那么显然的结论。

推论

(1 + x) ^ p \equiv 1 + x ^ p\pmod p

Lucas 定理

当 p 是质数时，

证明

设 n = dp + r\ (0\leq r < p)，则

(1 + x) ^ n = \ (1 + x) ^ {dp} (1 + x) ^ {r} \equiv \ (1 + x ^ p) ^ {d} (1 + x) ^ {r} \pmod p

由二项式定理，上式 x ^ m 前的系数即 \binom n m。

因为 (1 + x ^ p) ^ d 展开后 x 的次数均为 p 的倍数，(1 + x) ^ r 展开后 x 的次数小于 p，因此 x ^ m 项只能由 (1 + x ^ p) ^ d 展开后的 x ^ {\lfloor m / p \rfloor p} 项与 (1 + x) ^ r 展开后的 x ^ {m\bmod p} 项相乘得到。\square

另一种形式

设 n, m 在 p 进制下为 \sum_{i = 0} ^ c a_ip ^ i 和 \sum_{i = 0} ^ c b_ip ^ i，则

\binom n m \equiv \prod_{i = 0} ^ c \binom {a_i} {b_i} \pmod p

显然，两种形式是等价的。

根据 Lucas 定理，计算大组合数对 p 取模可拆成计算小组合数。\mathcal{O}(p) 预处理阶乘及其逆元做到 \mathcal{O}(1) 计算组合数，时间复杂度 \mathcal{O}(\log_p n)。模板题 P3807 代码。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e5 + 5;
int T, n, m, p, fc[N], ifc[N];
int ksm(int a, int b) {
  int s = 1;
  while(b) {
    if(b & 1) s = 1ll * s * a % p;
    a = 1ll * a * a % p, b >>= 1;
  }
  return s;
}
int binom(int n, int m) {
  return 1ll * fc[n] * ifc[m] % p * ifc[n - m] % p;
}
int lucas(int n, int m) {
  if(n % p < m % p) return 0;
  if(n < p) return binom(n, m);
  return 1ll * lucas(n / p, m / p) * binom(n % p, m % p) % p;
}
void solve() {
  cin >> n >> m >> p;
  for(int i = fc[0] = 1; i < p; i++) fc[i] = 1ll * fc[i - 1] * i % p;
  ifc[p - 1] = ksm(fc[p - 1], p - 2);
  for(int i = p - 2; ~i; i--) ifc[i] = 1ll * ifc[i + 1] * (i + 1) % p;
  cout << lucas(n + m, n) << endl;
}
int main() {
  cin >> T;
  while(T--) solve();
  return 0;
}

在 p 进制下考虑组合数取模是很有帮助的。计算大组合数对 p 取模的值，可以将 n, m 在 p 进制下的每一位分开考虑，再将所得结果相乘。特别地，若 n 在 p 进制下至少有一位小于 m，则 \binom n m \equiv 0 \pmod p，因为对 a_i < b_i 有 \binom {a_i} {b_i} = 0。这符合 1.6 小节的结论。

Lucas 定理还可以快速计算组合数奇偶性。\binom n m 是奇数当且仅当 m 在二进制下每一位均不大于 n，当且仅当 n 和 m 的按位与等于 m，当且仅当 n 和 m 的按位或等于 n。

4.2 扩展 Lucas 定理（exLucas）

当模数 p 不是质数时，也有快速计算 \binom n m \bmod p 的方法。

模合数的问题的第一步一定是 CRT，将问题简化为模指数幂的情况。具体地，设 p = \prod q_i ^ {k_i}，分别计算答案模 q_i ^ {k_i} 的结果，再使用 CRT 合并。这就是 CRT 的神力！

考虑 \binom n m \bmod {q ^ k}，自然地把组合数写成 \frac {n!}{m!(n - m)!}。因为 m!(n - m)! 含有质因数 q，所以无法求逆元。但因为模数只含质因数 q，所以我们考虑把 q 和其它质因数分开来算：求出组合数含有多少 q，以及分子和分母除掉其所包含的所有 q 之后的结果，即变形为

使用 Kummer 定理计算组合数的质因数幂次（v_q(n!) - v_q(m!) - v_q((n - m)!)）。此时分子和分母均不含 q，分别计算，再对分母求逆元即可。问题转化为 \frac {n!}{q ^ {v_q(n!)}} \bmod q ^ k，也就是阶乘去掉所有 q 之后对 q ^ k 取模。

设 d = \lfloor\frac n q\rfloor，d_k = \lfloor\frac n {q ^ k}\rfloor，r = n\bmod {q ^ k}。既然除掉了所有 q，自然想到将所有数分成 q 的倍数和不是 q 的倍数讨论。

对于 q 的倍数，有 q, 2q, \cdots, dq，我们给每个数除掉 q，问题变成求 \frac{d!}{q ^ {v_q(d!)}}。这是子问题。

对于不是 q 的倍数，把它们全部模掉 q ^ k，得到 d_k 组 1\sim q ^ k 内和 q 互质的数，以及一组 1\sim r 内和 q 互质的数。回忆扩展 Wilson 定理的符号，(n!)_q 表示 1\sim n 所有和 q 互质的数的乘积，所以只需计算 ((q ^ k!)_q ^ {d_k} \times (r!)_q) \bmod {q ^ k}。预处理 q ^ k 以内所有与 q 互质的数的前缀积，这部分可以 \mathcal{O}(\log n) 计算（快速幂）。进一步地，根据扩展 Wilson 定理，(q ^ k!)_q\bmod {q ^ k} 等于 1 或 -1，所以不需要快速幂。

综上，

当 n < q 时，直接返回预处理结果，否则使用递归式计算。时间复杂度 \mathcal{O}(\log_q n)。

• 注意：递归的子问题是除以 q，而循环节数量是除以 q ^ k。
• 注意：区分 \frac {n!} {q ^ {v_q(n!)}} 和 (n!)_q。前者只是将所有 p 去掉，而后者将含有质因数 p 的所有数去掉了。

综上，我们在 \mathcal{O}(\omega(p)\log n + \sum {q_i} ^ {k_i}) 的时间内求出一个大组合数模任意数 p 的值。若模数固定且预处理，则可以做到单次 \mathcal{O}(\omega(p)\log n)。模板题 P4720 代码。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void exgcd(int a, int b, int &x, int &y) {
  if(!b) return x = 1, y = 0, void();
  exgcd(b, a % b, y, x), y -= a / b * x;
}
int inv(int x, int p) {
  return exgcd(x, p, x, *new int), (x % p + p) % p;
}
ll n, m;
int p, tp, ans, curp = 1, q, qk, fc[1000005];
ll num(ll n) {
  ll s = 0;
  while(n) s += n /= q;
  return s;
}
int calc(ll n) {
  if(!n) return 1;
  return 1ll * calc(n / q) * (tp && (n / qk & 1) ? qk - 1 : 1) % qk * fc[n % qk] % qk;
} // 注意 n / q 和 n / qk!
int solve() {
  tp = (qk & 1) || qk <= 4; // 扩展 Wilson 定理.
  for(int i = fc[0] = 1; i < qk; i++) fc[i] = 1ll * fc[i - 1] * (i % q ? i : 1) % qk;
  int pw = num(n) - num(m) - num(n - m);
  int res = 1ll * calc(n) * inv(1ll * calc(m) * calc(n - m) % qk, qk) % qk;
  while(pw--) res = 1ll * res * q % qk; // 根据 Kummer 定理, 质因子在组合数中的个数为对数级别.
  return res;
}
int main() {
  cin >> n >> m >> p;
  for(int i = 2; i <= p; i++) {
    if(i * i > p) i = p;
    if(p % i == 0) {
      q = i, qk = 1;
      while(p % i == 0) qk *= i, p /= i;
      ans += 1ll * (solve() - ans % qk + qk) * inv(curp, qk) % qk * curp;
      ans %= (curp *= qk); // exCRT 合并更方便.
    }
  }
  cout << ans << endl; 
  return 0;
}

4.3 例题

[BZOJ2445] 最大团

定义一张 n 个点的图是 “好图” 当且仅当它能被分成若干大小相等的完全图。结点有标号。记 n 个点的好图个数为 G(n)。求 m ^ {G(n)}\bmod 999999599。n, m\leq 2\times 10 ^ 9。

模数是质数，Fermat 小定理转化为求 G(n)\bmod (10 ^ 9 - 402)。

被分成的完全图大小 d 是 n 的因数，考虑枚举 d\mid n 并计算完全图大小为 d 时的方案数。

根据组合意义，从 n 个节点中选出 d 个点连成完全图，再从剩下 n - d 个节点中选出 d 个点连成完全图，以此类推。最后剩下的 d 个节点连成完全图。由于完全图之间无序，而我们枚举完全图的过程有序，因此要除以 \frac n d 的阶乘。记 c = \dfrac n d，则

观察 99999598，将其分解质因数后得到 2\times 13\times 5281\times 7283，模数是 square-free number。考虑分别求上式对这四个质数取模后的结果，再 CRT 合并。问题转化为计算答案对质数 p 取模后的结果，其中 p 较小。

根据 1.6 小节的结论，先求出答案含有多少个质因子 p，若个数不为 0 则直接返回 0。否则问题转化为计算一个数的阶乘去掉所有质因子 p 后模 p 的结果，使用 exLucas 即可。代码。

*P5598 【XR-4】混乱度

设 S(l, r) 表示 a 的区间和，根据组合意义得到

固定 l，考虑 r 在增大的过程中，S(l, r) 不断增加。根据 Lucas 定理，一旦 S(l, r) 在 p 进制下进位，那么之后的 f(l, r)\bmod p 均为 0。因此，在经过至多 p\log_p V 个非零的 a_r 后，f(l, r) 对答案不再有贡献。

预处理每个非零的 a_r 在 p 进制下有哪些位非零以及这一位上的值，对每个 l，维护当前 S(l, r) 在 p 进制下每一位的值，可快速计算 \binom {S(l, r)}{S(l, r - 1)}。考虑到 a_r = 0 时 f(l, r - 1) = f(l, r)，所以对每个位置预处理下一个非零的位置即可快速跳过等于 0 的位置。

时间复杂度 \mathcal{O}(np\log_pn)。代码。

5. 离散对数问题

离散对数问题即求解 离散对数方程

其中 x 即模 p 下的 \log_a b。解可能不存在，也可能存在多个，我们只要求出任意一个。

5.1 大步小步算法（BSGS）

大步小步算法（Baby Step Giant Step，BSGS）要求 a\perp p。

BSGS 使用了 meet-in-the-middle：设块长为 M 且 x = AM - B，则 a ^ {AM} \equiv ba ^ B \pmod p。因为 a \perp p，所以若 a ^ {AM} \equiv ba ^ B\pmod {p}，则 a ^ {AM - B} \equiv b\pmod p。枚举 a ^ {AM} 与 ba ^ B 所有可能的取值，并通过哈希表判断是否存在 A, B 使得这两个值相等。时间复杂度 \mathcal{O}(\max(A, B))。

根据 Euler 定理，若有解，则在 [0, p - 2] 上有解，所以 1\leq B \leq M，1\leq A\leq \lceil\frac{p - 1} M \rceil。将阈值 M 设为 \sqrt{p} 得到最优复杂度 \mathcal{O}(\sqrt{p})。模板题 P3846 代码。

#include <bits/stdc++.h>
using namespace std;
int BSGS(int a, int b, int p) {
  int A = 1, B = sqrt(p) + 1;
  a %= p, b %= p;
  unordered_map<int, int> mp;
  for(int i = 1; i <= B; i++) {
    A = 1ll * A * a % p;
    mp[1ll * A * b % p] = i;
  }
  for(int i = 1, AA = A; i <= B; i++) {
    if(mp.find(AA) != mp.end()) {
      return i * B - mp[AA];
    }
    AA = 1ll * AA * A % p;
  }
  return -1;
}
int main() {
  int p, b, n;
  cin >> p >> b >> n;
  int ans = BSGS(b,n,p);
  if(~ans) cout << ans << "\n";
  else puts("no solution");
  return 0;
}

根据枚举顺序可知以上代码求得 \log_a b 的最小的非负整数解。解的循环节长度为最小的正整数 y 使得 a ^ y\equiv 1\pmod p，即 \delta_p(a)，见 6.1 小节。

5.2 扩展大步小步算法（exBSGS）

对于更一般的离散对数方程，没有 a\perp p 的条件，该怎么办呢？

从已知到未知。既然可以解决 a\perp p，那么我们尝试把 a,p 凑成互质。同余式两侧同时除以 d = \gcd(a, p)，方程化为 \frac a d a ^ {x - 1} \equiv \frac b d \pmod{\frac p d}。若 d \nmid b 显然无解。

注意到 \frac a d \perp \frac p d，所以前者在模后者下存在逆元。p 可能不是质数，需要使用 exgcd 求逆元。移项，方程变为 a ^ {x - 1} \equiv \frac b d \times (\frac a d) ^ {-1} \pmod {\frac p d}，等式右边为常数。

因为 a 和 \frac p {\gcd(a, p)} 可能不互质，所以重复上述操作直到 a, p 互质，此时直接使用 BSGS 求解即可。设提出的 a 的数量为 k，则求出的解需要加上 k。注意在每次操作开始前特判 b = 1，此时答案恰等于已经提出的 a 的数量。

显然 k = \mathcal O(\log p)，时间复杂度 \mathcal{O}(\sqrt p)。模板题 SP3105 代码。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
int a, p, b;
void exgcd(int a, int b, int &x, int &y) {
    if(!b) return x = 1, y = 0, void();
    exgcd(b, a % b, y, x), y -= a / b * x;
}
int inv(int x, int p) {return exgcd(x, p, x, *new int), (x % p + p) % p;}
int BSGS(int a, int b, int p) {
    a %= p, b %= p;
    int A = 1, B = sqrt(p) + 1;
    gp_hash_table <int, int> mp;
    for(int i = 1; i <= B; i++) mp[1ll * (A = 1ll * A * a % p) * b % p] = i;
    for(int i = 1, AA = A; i <= B; i++, AA = 1ll * AA * A % p) if(mp.find(AA) != mp.end()) return i * B - mp[AA];
    return -1;
}
int exBSGS(int a, int b, int p) {
    int d = __gcd(a, p), cnt = 0;
    a %= p, b %= p;
    while(d > 1) {
        if(b == 1) return cnt;
        if(b % d) return -1;
        p /= d, b = 1ll * b / d * inv(a / d, p) % p;
        d = __gcd(p, a %= p), cnt++;
    }
    int ans = BSGS(a, b, p);
    return ~ans ? ans + cnt : -1;
}
int main() {
    cin >> a >> p >> b;
    while(a) {
        int ans = exBSGS(a, b, p);
        if(~ans) cout << ans << "\n";
        else puts("No Solution");
        cin >> a >> p >> b;
    }
    return 0;
}

5.3 例题

P2485 [SDOI2011] 计算器

操作 1 快速幂，操作 2 exgcd 求逆元，操作 3 BSGS。

P3306 [SDOI2013] 随机数生成器

把 x 的坐标左移一位，显然有 x_i = a ^ ix_0 + b\sum_{j = 0} ^ {i - 1} a ^ j。由等比数列求和公式，

对同余式进行简单变形后得到离散对数问题，使用 BSGS 求解。时间复杂度 \mathcal{O}(T\sqrt p)。代码。

6. 阶与原根

对于含乘法的同余式 ab\equiv c\pmod m，如果能找到 g, x, y, z 使得 g ^ x\equiv a\pmod m，g ^ y\equiv b\pmod m，g ^ z\equiv c \pmod m，那么根据 Euler 定理，同余式等价于 x + y\equiv z\pmod {\varphi(m)}。也就是说，我们希望找到一个共同的底，将幂次的乘法化为指数上的加法。

在模数是合数时，一般会将问题化为只考虑和模数互质的数。m\ (m \geq 2) 的简化剩余系在模 m 的乘法下构成群（封闭、结合律、逆元、单位元）。借用群相关的定义，得到阶和原根（循环群的生成元）的概念。

对 a\perp m，如果 a 的幂次模 m 可以取到整个简化剩余系，那么称 a 是 m 的原根。可以发现 a 就是上述问题的一个较为可行的底，因为所有和 m 互质的数都可以用它的幂次表示。

6.1 阶及其性质

定义

考虑一个数自身相乘时，它的阶如何变化。如果我们将模 m 下 a 的幂次看成一个长为 \delta_m(a) 的环，那么 a 的幂次相当于在环上每次跳一步，a ^ k 的幂次相当于在环上每次跳 k 步。使用 1.7 小节的结论即可。

性质 2

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

证明

注意到 (a ^ k) ^ x = a ^ {kx}。

对于第一部分，根据性质 1，\delta_m(a ^ k) 为最小的 x 使得 \delta_m(a) \mid kx。于是 x_{\min} = \frac {\delta_m(a)}{\gcd(\delta_m(a), k)}（见最开头的基本知识）。

对于第二部分，同时是 k 和 \delta_m(a) 的倍数的最小正整数为 \operatorname{lcm}(\delta_m(a), k)，所以使得 a ^ {kx} \equiv 1\pmod m 的最小的 kx 即 \operatorname{lcm}(\delta_m(a), k)。于是 x_{\min} = \frac {\operatorname{lcm}(\delta_m(a), k)}{k}。

以上两部分也可以根据 ab = \gcd(a, b) \times \mathrm{lcm}(a, b) 相互推导。\square

考虑两个数相乘时，它们的阶如何变化。和一个数自身的幂次 \delta_m(a ^ k) \leq \delta_m(a) 不一样，乘积的阶可能小于其中每个因子的阶，也可能大于。我们需要知道这种变化是由什么引起的。从循环节的角度考虑会带给我们一些启发：乘积的阶变小是由于其两个因子的阶的公共因数，乘积的阶变大是由于其两个因子的阶的非公共因数。

如果 \delta_m(a) = \delta_m(b)，那么 \delta_m(ab) 可以是 \delta_m(a) 的任何因数。\delta_m(g) = \delta_m(g ^ 2) = \delta_m(g ^ 4) = \delta_m(g ^ {14}) = 15，而 \delta_m(g \cdot g ^ {14}) = 1，\delta_m(g \cdot g ^ 4) = 3，\delta_m(g \cdot g ^ 2) = 5，\delta_m(g\cdot g) = 15。

性质 3

**证明** 必要性是显然的。 充分性的证明思路是注意到对所有 $\delta_m(a)$ 的倍数或 $\delta_m(b)$ 的倍数但不为 $\operatorname{lcm}(\delta_m(a), \delta_m(b)) = \delta_m(a)\delta_m(b)$ 的倍数 $x$，对于 $a ^ x\bmod m$ 和 $b ^ x\bmod m$，一定恰有一个等于 $1$，另一个不等于 $1$，所以 $x$ 一定不是 $\delta_m(ab)$ 的倍数。 两个最小循环节分别为 $\delta_m(a)$ 和 $\delta_m(b)$ 的序列相乘，一定有 $L = \delta_m(a)\delta_m(b)$ 的循环节，最小循环节显然是 $L$ 的因数。如果最小循环节不等于 $L$，那么存在 $L$ 的质因数 $p$ 使得 $(ab) ^ {L / p} \equiv 1\pmod m$。不妨设 $p\mid \delta_m(b)$，则 $\frac L p = k\delta_m(a)$，其中 $k = \frac {\delta_m(b)} p$。因为 $\delta_m(a)\perp \delta_m(b)$，所以 $k\delta_m(a)$ 不是 $\delta_m(b)$ 的倍数。但 $1\equiv (ab) ^ {k\delta_m(a)} \equiv b ^ {k\delta_m(a)} \pmod m$，矛盾。这说明最小循环节等于 $L$。$\square

对于更一般的情况呢？读者可以先结合以上两种特殊情况自行思考。

性质 4

对于质因数 p，如果它在 \delta_m(a) 和 \delta_m(b) 的次数相等，那么它在 \delta_m(ab) 的次数是任意的，但不会超过它在 \delta_m(a) 的次数。如果不等，那么它在 \delta_m(ab) 的次数是它在 \delta_m(a) 和 \delta_m(b) 的次数的较大值。

可以这样类比：设 p 在 a 的次数为 x，在 b 的次数为 y。如果 x = y，那么 p 在 a + b 的次数 z\geq x 可以任意大。如果 x\neq y，那么 z = \min(x, y)。至于为什么是加法，考虑到阶本身是描述指数循环节的，而相乘转化到指数上就是加法。

如果 m 有原根 g，那么一切都是好理解的：\delta_m(ab) = \frac {\varphi(m)} {\gcd(\varphi(m), \log_g a + \log_g b)}，指数在分母上解释了一个是任意小一个是任意大，一个是较大值一个是较小值。

性质 4 描述了乘积的阶与每个因子的阶的关系。

性质 2 和性质 4 给予我们操作阶的空间，并引出了以下性质。

性质 5

给定 a, b\perp m，存在 c 使得 \delta_m(c) = \operatorname{lcm}(\delta_m(a), \delta_m(b))。

证明

对每个质因数 p，如果 p 在 \delta_m(a), \delta_m(b) 的次数相等且不为 0，那么让 a\gets a ^ p。由性质 2，因为 p\mid \delta_m(a)，所以 \delta_m(a ^ p) = \frac {\delta_m(a)} p。处理后 \delta_m(a') 和 \delta_m(b) 没有次数相同的质因数。根据性质 4 可知 \delta_m(a'b) = \operatorname{lcm}(\delta_m(a), \delta_m(b))。\square

离散对数的通解形式：当 a\perp m 时，使得 a ^ x\equiv b\pmod m 的 x 若存在，则其循环节恰为 \delta_m(a)。可以求出最小和次小的解 x_1, x_2，则通解形式为 x = x_1 + k(x_2 - x_1)\ (k\in \N)。也可以先把阶求出来。

求法

法一：使用 BSGS 求 a ^ x\equiv 1 \pmod m 的最小正整数解。

法二：根据性质 1，对 x = k\delta_m(a) 有 a ^ x \equiv 1\pmod m。考虑令 x = \varphi(m)，对于 \varphi(m) 的每个质因子 p，用 x 不断试除 p 直到 x 无法整除 p 或 a ^ {x / p} \not \equiv 1\pmod m。时间复杂度为分解质因数加上 \mathcal{O}(\log ^ 2 m)。

6.2 原根

以下设 m\geq 2 且 a\perp m。

定义

若 \delta_{m}(a) = \varphi(m)，则称 a 为模 m 的 原根。并不是所有数都有原根。存在原根的模 m 的缩系同构于循环群：原根等价于循环群的生成元。

我们需要原根是因为它可以 生成 模 m 的缩系，即它的若干次幂在模 m 下取遍了所有与 m 互质的数。这使得我们在考虑解与模数互质且模数存在原根的同余方程时可以用原根的若干次幂代替未知数，在求解高次剩余时非常有用。

简单地说，它可以将乘法转化为加法。

性质

判定原根的一般方法是直接计算阶。如果 \delta_m(a)\neq \varphi(m)，那么一定存在 \varphi(m) 的质因数 p 使得 \frac {\varphi(m)} {p} 是 \delta_m(a) 的倍数，即 a ^ {\varphi(m) / p}\equiv 1 \pmod m。

原根判定定理

除了判断一个数是否是原根，我们还需要判断一个数是否有原根。

原根存在定理

证明较复杂，不感兴趣的读者可以跳过。 $2, 4$ 有原根是显然的。 **奇质数** 对奇质数 $p$，由引理 5，存在 $g$ 使得对任意 $1\leq i < p$，$\delta_p(i) \mid \delta_p(g)$，所以 $x ^ {\delta_p(g)}\equiv 1\pmod p$ 有 $p - 1$ 个不同的解。由 Lagrange 定理，$\delta_p(g) = p - 1$。 **奇质数幂** 考虑数学归纳。 设 $g$ 是奇质数 $p$ 的原根。如果 $g ^ {p - 1}\equiv 1\pmod {p ^ 2}$，那么 $$ (g + p) ^ {p - 1} \equiv g ^ {p - 1} + (p - 1)g ^ {p - 2}p \equiv 1 - pg ^ {-1} \not\equiv 1\pmod {p ^ 2} $$ 设 $g$ 是奇质数幂 $p ^ \alpha$ 的原根，$1\leq k < p$，且 $g ^ {p ^ {\alpha - 1}(p - 1)} \equiv 1 + kp ^ {\alpha} \pmod {p ^ {\alpha + 1}}$（当 $\alpha = 1$ 时，上述说明保证这样的 $g$ 存在），那么 $$ g ^ {p ^ {\alpha - 1}(p - 1)} \equiv 1 + (k + cp)p ^ \alpha \pmod {p ^ {\alpha + 2}} $$ 于是 $$ g ^ {p ^ {\alpha}(p - 1)} \equiv (1 + (k + cp)p ^ \alpha) ^ p\equiv 1 + kp ^ {\alpha + 1} \pmod {p ^ {\alpha + 2}} $$ 且 $g$ 是奇质数幂 $p ^ {\alpha + 1}$ 的原根。由数学归纳法可知 $g$ 是任意 $p ^ {\alpha} \ (\alpha \geq 1)$ 的原根。 - 请思考以上推导过程在哪里对 $p = 2$ 不适用。 设 $g$ 是 $p ^ \alpha$ 的原根，考虑 $g \bmod p ^ {\alpha}$ 可知 $\delta_{2p ^ \alpha}(g) \geq \delta_{p ^ {\alpha}}(g) = \varphi(p ^ \alpha) = \varphi(2p ^ \alpha)$。所以 $g$ 是 $2p ^ {\alpha}$ 的原根。 **必要性** 首先，如果 $m$ 有原根，那么 $m$ 的所有因数都有原根。所以只需证明 $8$，$4p$ 和 $p_1p_2$ 没有原根。$8$ 没有原根是显然的。 对任意 $x\perp 4p$，因为 $\varphi(p)$ 是 $\varphi(4) = 2$ 的倍数，所以 $x ^ {\varphi(p)} \equiv 1 \pmod p$ 且 $x ^ {\varphi(p)} \equiv 1\pmod 4$。由 CRT，$x ^ {\varphi(p)} \equiv 1\pmod {4p}$。 对任意 $x\perp p_1p_2$，因为 $\varphi(p_1), \varphi(p_2)$ 都是 $2$ 的倍数，所以 $x ^ {\varphi(p_1p_2) / 2} \equiv 1\pmod {p_1}$ 且 $x ^ {\varphi(p_1p_2) / 2} \equiv 1\pmod {p_2}$。由 CRT，$x ^ {\varphi(p_1p_2) / 2}\equiv 1\pmod {p_1p_2}$。$\square

如果一个数有原根，那么其缩系上的乘法等价于模 \varphi(m) 下的加法：将缩系的每个数变成原根的幂次，两个数相乘是同底数幂相乘，指数相加。这提供了更多阶的性质。

性质 6

若 m 有原根，则使得 \delta_m(a) = l 的 a 的个数为

\begin{cases} 0 & l \nmid \varphi(m) \\ \varphi(l) & l \mid \varphi(m) \end{cases}

证明

根据性质 1，第一部分显然。考虑第二部分。

设 g 是 m 的原根。因为任意 a\perp m 均可表示为 g ^ k\ (0\leq k < \varphi(m))，所以答案即使得 \delta_m(g ^ k) = l 的 k 的个数。根据性质 2，\delta_m(g ^ k) = \frac {\delta_m(g)}{\gcd(\delta_m(g), k)}，因此 \frac {\varphi(m)}{\gcd(\varphi(m), k)} = l，即 \gcd(\varphi(m), k) = \frac {\varphi(m)}l。由基本知识，k 的个数为 \varphi(\frac {\varphi(m)} {\varphi(m) / l}) = \varphi(l)。\square

形象地，将 g ^ k \bmod m\to g ^ {k + 1}\bmod m 看成长度为 \varphi(m) 的环。在环上每次走 k 步形成子环，则 g ^ k 的阶等于子环环长。由 1.7 小节，环长为 \frac n {\gcd(n, k)}。为使 \frac{\varphi(m)}{\gcd(\varphi(m), k)} = l，则 \gcd(\varphi(m), k) = \frac {\varphi(m)}{l}。

性质 6 反映了欧拉函数的性质 \sum_{d \mid n} \varphi(d) = n。\sum_{l \mid \varphi(m)} \varphi(l) = \varphi(m)，即模 m 的阶等于 l 的数的个数之和（模 m 下存在阶的数的个数）等于和 m 互质的数的个数，而和 m 互质是在模 m 下存在阶的充要条件。

原根个数定理

若正整数 m 有原根，则原根个数为 \varphi(\varphi(m))。

求法

求一个数的所有原根：求出任意一个原根 g，根据性质 2，g ^ k\bmod m\ (k \perp \varphi(m)) 也是 m 的原根。相当于在长为 \varphi(m) 的环上每次走 k 步，因为 k\perp \varphi(m)，所以一定走遍整个环。

中国数学家王元证明了质数的最小原根的数量级为 \mathcal{O}(m ^ {0.25 + \epsilon})（1959，需要指出的是大 O 符号仅表示上界）。结合原根存在定理的推导过程，可以证明任何有原根的数最小原根不超过这个数量级。再根据原根判定定理，可以 \mathcal{O}(m) 预处理每个数的最小质因子后 \mathcal{O}(m ^ {0.25}\omega(m)\log m) 求出 m 的最小原根，从而求出 m 的所有原根。模板题 P6091 代码。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e6 + 5;
int ksm(int a, int b, int p) {
  int s = 1;
  while(b) {
    if(b & 1) s = 1ll * s * a % p;
    a = 1ll * a * a % p, b >>= 1;
  }
  return s;
}
void solve() {
  int n, d;
  cin >> n >> d;
  int x = n, phi = n;
  for(int i = 2; i <= x; i++) {
    if(x % i == 0) {
      phi = phi / i * (i - 1);
      while(x % i == 0) x /= i;
    }
  }
  vector<int> pr;
  x = phi;
  for(int i = 2; i <= x; i++) {
    if(x % i == 0) {
      pr.push_back(i);
      while(x % i == 0) x /= i;
    }
  }
  for(int i = 1; i < n; i++) {
    if(__gcd(i, n) != 1) continue;
    bool ok = 1;
    for(int it : pr) {
      ok &= ksm(i, phi / it, n) != 1;
    }
    if(ok) {
      static int is[N], g[N];
      memset(is, 0, N << 2);
      is[i] = 1;
      for(int j = 2; j <= phi; j++) {
        if(__gcd(j, phi) == 1) {
          is[ksm(i, j, n)] = 1;
        }
      }
      int cnt = 0;
      for(int j = 1; j <= n; j++) {
        if(is[j]) g[++cnt] = j;
      }
      cout << cnt << "\n";
      for(int p = 1; p <= cnt / d; p++) {
        cout << g[p * d] << " ";
      }
      cout << "\n";
      return;
    }
  }
  cout << "0\n\n";
}
int main() {
  int T;
  cin >> T;
  while(T--) solve();
  return 0;
}

补充：因为 \frac n {\varphi(n)} 是 \mathcal{O}(\log \log n) 级别，所以 \frac n {\varphi(\varphi(n))} = \mathcal{O}((\log \log n) ^ 2)。如果每次在 1\sim m - 1 中均匀随机选择一个数，那么期望随机 \mathcal{O}((\log \log m) ^ 2) 次得到一个原根，比 \mathcal{O}(m ^ {0.25}) 更好。

原根和单位根

若 m 有原根 g，设 n = \varphi(m)，则 m 的简化剩余系与 n 次单位根 同构。

对于任何 a \perp m，其可以写成 g ^ k。任何一个 n 次单位根也可以写成 \omega_n ^ k。同时 g ^ n \equiv 1\pmod p 且 omega_n ^ n = 1。因此，我们可以将单位圆应用在 m 的简化剩余系上，为原根提供了一个形象的表示方法，如下图。

图中，单位根的 0\sim 9 次幂等分单位圆。\omega_n ^ i \times \omega_n ^ j = \omega_n ^ {(i + j)\bmod 10} 对应 g ^ i\times g ^ j \equiv g ^ {(i + j)\bmod 10}\pmod {11}，环上运算（两个数相乘）的循环往复（逆时针旋转）体现了 “模” 的操作。

因此，对于特定模数，我们可以使用原根代替 n 次单位根进行快速傅里叶变换 FFT。当需要使用 2 ^ k 次单位根时，若 2 ^ k\mid \varphi(p) 且 p 有原根，可使用原根代替 2 ^ k 次单位根，即快速数论变换 NTT。常见模数 998244353 的 Euler 函数 \varphi(998244353) = 2 ^ {22}\times 238。

类比原根和单位根，得到以下性质。

性质 7

设 p 是奇质数或奇质数的幂，g 是 p 的原根，则 g ^ {\varphi(p) / 2} \equiv -1 \pmod p。

证明

设 g ^ x \equiv -1\pmod p，则 x\neq \varphi(p)。如果 x\neq \frac {\varphi(p)} 2，那么 (g ^ x) ^ 2 = g ^ {2x}\not\equiv 1\pmod p，和 g ^ x \equiv -1\pmod p 矛盾。因此 \log_p -1 = \frac {\varphi(p)} 2。\square

性质 7 在二次剩余部分有用。

*6.3 (\mathbb Z / n\mathbb Z) ^ \times 的结构

关于记号，见 1.10 小节。

根据 CRT，我们只需要考虑 (\mathbb Z / p ^ k\mathbb Z) ^ \times 的结构。

根据原根的定义，(\mathbb Z / p ^ k\mathbb Z) ^ \times 是循环群当且仅当 p ^ k 有原根。对奇质数 p，已知 p ^ k 有原根，所以 (\mathbb Z / p ^ k\mathbb Z) ^ \times 一定是循环群。实际上，证明 (\mathbb Z / p ^ k\mathbb Z) ^ \times 和证明 p ^ k 有原根等价。笔者在查阅资料时找到了一篇分析 (\mathbb Z / n\mathbb Z) ^ \times 的结构的论文，其中直接证明 (\mathbb Z / p ^ k\mathbb Z) ^ \times 是循环群的推导过程和以上证明 p ^ k 有原根是几乎一致的。

考虑 (\mathbb Z / 2 ^ k\mathbb Z) ^ \times 的结构。当 k = 1 或 k = 2 时平凡。读者可以先猜一猜结果会是什么样。由有限生成阿贝尔群基本定理，(\mathbb Z / 2 ^ k\mathbb Z) ^ \times 同构于若干循环群的直积，如果有一个元素的阶是 2 ^ {k - 2}，那么 (\mathbb Z / 2 ^ k\mathbb Z) ^ \times 只能是 Z_2 \times Z_{2 ^ {k - 2}}，因为 |(\mathbb Z / 2 ^ k\mathbb Z) ^ \times| = 2 ^ {k - 1}。

事实上，5 就是这样的元素。

引理 1

对 k \in \N，5 ^ {2 ^ k} - 1 恰含有 k + 2 个质因数 2。

证明

当 k = 0 时命题成立。5 ^ {2 ^ {k + 1}} - 1 = (5 ^ {2 ^ k} - 1)(5 ^ {2 ^ k} + 1)，前一项恰因子含有 k + 2 个质因数 2，是 4 的倍数，所以后一项因子不是 4 的倍数。因此 5 ^ {2 ^ {k + 1}} - 1 恰含有 k + 3 个质因数 2。\square

引理 2

对 k\geq 3，\delta_{2 ^ k}(5) = 2 ^ {k - 2}。

证明

因为阶是 2 ^ {k - 1} 的因数但不能等于 2 ^ {k - 1}（没有原根），所以 \delta_{2 ^ k}(5)\mid 2 ^ {k - 2}。如果 5 ^ {2 ^ {k - 3}}\equiv 1\pmod {2 ^ k}，那么 5 ^ {2 ^ {k - 3}} - 1 含有至少 k 个质因数 2，和引理 1 矛盾。因此 \delta_{2 ^ k}(5) = 2 ^ {k - 2}。\square

现在我们知道 5 是 Z_{2 ^ {k - 2}} 这一项的生成元，那么 Z_2 这一项的生成元是什么？找一个阶为 2 的元素，也就是找一个不是 1 但平方是 1 的数。我们知道这样的数有 3 个，-1 是其中之一，那么 -1 是否合法呢？

引理 3

对 k\geq 2 和 m\in \N，5 ^ m\not\equiv -1\pmod {2 ^ k}。

证明

如果成立，那么 5 ^ m\equiv -1\pmod 4，但 5 ^ m\equiv 1 ^ m\equiv 1\pmod 4，矛盾。\square

上述推导说明 (\mathbb Z / 2 ^ k\mathbb Z) ^ \times\cong Z_2\times Z_{2 ^ {k - 2}}，其中生成元分别是 -1 和 5。于是得到以下结论。

性质 8

对任意 k\geq 3 和 a\perp 2，存在 c\in [0, 1] 和 d\in [0, 2 ^ {k - 2} - 1] 使得 a \equiv (-1) ^ c 5 ^ d\pmod {2 ^ k}，且这种表示唯一，即每个 a\in [0, 2 ^ k - 1] 的奇数唯一对应一组 (c, d)。

性质 8 是求模 2 ^ k 下的 N 次剩余的关键结论。

现在让我们站在更高的视角看看为什么 2 ^ k\ (k\geq 3)，4p\ (p\perp 2) 和 pq\ (p, q\perp 2) 没有原根：由 CRT，对 n\perp m，(\mathbb Z / nm\mathbb Z) ^ \times \cong (\mathbb Z / n\mathbb Z) ^ \times \times (\mathbb Z / m\mathbb Z) ^ \times，于是

由 3.3 小节，如果 n 和 m 不互质，那么 Z_n\times Z_m 一定不是循环群，所以这些数对应的模意义下的乘法群都不是循环群，自然没有原根。

6.4 例题

P5605 小 A 与两位神仙

前置知识：Pollard-rho（数论 III）。

模数 p 是奇质数的幂，存在原根 g。

尝试将 x 和 y 写成 g ^ X 和 g ^ Y。根据欧拉定理，x ^ a \equiv y\pmod p 等价于方程 Xa\equiv Y\pmod {\varphi(p)}。根据 Bezout 定理，后者有解的充要条件是 \gcd(X, \varphi(p)) \mid Y，这等价于 \gcd(X, \varphi(p)) \mid \gcd(Y, \varphi(p))。根据阶的性质 \delta_p(g ^ k) = \frac {\delta_p(g)}{\gcd(\delta_p(g), k)}，我们发现 \delta_p(x) = \frac {\varphi(p)} {\gcd(\varphi(p), X)}，因此条件又等价于 \delta_p(y)\mid \delta_p(x)。

直接求阶即可，需要使用 Pollard-rho 分解 \varphi(p)，时间复杂度 \mathcal{O}(n\log ^ 2p + p ^ {0.25})。

本题告诉我们的结论：对于奇质数幂 p ^ \alpha 和 x, y\perp p，x ^ a\equiv y\pmod {p ^ \alpha} 有解当且仅当 \delta_{p ^ \alpha}(y)\mid \delta_{p ^ {\alpha}}(x)。

*P6730 [WC2020] 猜数游戏

和上一题差不多的思路。

分成 a 与 p 互质和 a 与 p 不互质两种情况考虑。并且将每个数的贡献拆开来考虑，即求出有多少种情况使得 a 对答案有贡献。

当且仅当 S 中不存在一个数能生成 a 时，a 对答案有贡献。因此对每个 a，答案加上 2 ^ {n - c}，其中 c 是能生成 a 的数的个数。

当 a 与 p 不互质时，因为 p 是奇质数的幂，所以在不超过 \log 次后 a 的幂变为 0，因此直接考虑每个数能生成哪些数即可得到每个数能被多少个数生成。使用哈希表存储，该部分时间复杂度 n\log p。

当 a 与 p 互质时，直接使用上一题的结论，对每个数求阶后做高维后缀和即可。注意若两个数能互相生成，即阶相等，则需要钦定一个顺序，使得前面的数钦定生成后面的数。

7. N 次剩余问题

N 次剩余问题即求解形如 x ^ n\equiv a\pmod p 的方程。注意未知数 x 在底数上，而离散对数问题的未知数在指数上。

7.1 定义与符号

对 p\nmid a，若存在整数 x 使得 x ^ n\equiv a\pmod p，则称 a 是 p 的 n 次剩余。

特别地，对 p\nmid a，若存在整数 x 使得 x ^ 2 \equiv a\pmod p，则称 a 是 p 的 二次剩余，反之称 a 为 p 的 二次非剩余。注意，这两个定义基于 a 不是 p 的倍数，也就是说，如果 a 是 p 的倍数，那么 a 既不是 p 的二次剩余，也不是 p 的二次非剩余。

Legendre 符号：记作 (\frac a p)。当 a 是 p 的二次剩余时，该值为 1；当 a 是 p 的二次非剩余时，该值为 -1；当 a 是 p 的倍数时，该值为 0。

7.2 二次剩余的分布

奇质数

当 p 是奇质数时，二次剩余非常容易理解。如果 a 是 p 的二次剩余，那么 a \equiv x ^ 2\pmod p。用原根表示 a 和 x，设 a \equiv g ^ d\pmod p，x \equiv g ^ k\pmod p，那么 g ^ d \equiv g ^ {2k}\pmod p，即 d\equiv 2k \pmod {p - 1}。因为 p - 1 是偶数，所以 d 必须是偶数，否则无解。当 d 是偶数时，k 有两个解（1.3 小节应用部分），每个 k 对应一个 x \equiv g ^ k \pmod p。

也就是说，原根的偶数次幂和奇数次将 1\sim p - 1 分成两类，偶数次幂对应二次剩余，奇数次幂对应二次非剩余。因此，二次剩余和二次非剩余的数量均为 \frac {p - 1} 2。这和原根的选择无关，也就是说，任意原根的偶数次幂集合都是相同的。

进一步地，如果 x_0 和 x_1 都是 a 的平方根，那么由平方差公式，(x_0 + x_1)(x_0 - x_1)\equiv 0\pmod p。因为 p 是质数，所以 x_0 + x_1 \equiv 0 \pmod p，即 x_0 和 x_1 互为相反数。从原根的角度分析，x_0 和 x_1 写成以 g 为底的幂时在指数上相差 \frac {p - 1} 2，而 g ^ {(p - 1) / 2} \equiv 1\pmod p。另一种角度是如果 x ^ 2\equiv a\pmod p，那么 (-x) ^ 2\equiv a\pmod p。

类比：正数（二次剩余）的平方根有两个且互为相反数，负数（二次非剩余）没有平方根。

奇质数幂

将奇质数的结论稍微推广即可，读者可以先自行尝试推导结论。