
在初等数论里,加减乘除都还算听话。一到除法,同余式就不成立了:6 \equiv 0 \pmod 3,但两边同时除以 2 得到 3 \equiv 0 \pmod 3,已经不是同余了。想让除法也有意义,就要引入逆元。
这一章讲的就是模运算下的「除法」,以及围绕它建立起来的几个经典定理。它们是 CSP-S 提高级的正式考点。
本章的知识点与 GESP、CSP-J/S 大纲的对应关系如下。
| 考试 | 大纲要求 | 本章位置 |
|---|---|---|
| NOI 提高级 | 2.5.2 初等数论:同余式、欧拉定理与欧拉函数、费马小定理、威尔逊定理、裴蜀定理、模运算意义下的逆元、扩展欧几里得算法、中国剩余定理 | 全章 |
同余式
若 a - b 能被 m 整除,就说 a 与 b 模 m 同余,记作:
a \equiv b \pmod m
同余式可以像等式一样做加、减、乘:若 a \equiv b、c \equiv d \pmod m,则
a + c \equiv b + d \pmod ma - c \equiv b - d \pmod ma \times c \equiv b \times d \pmod m
唯独除法不能随便用。a \times c \equiv b \times c \pmod m 推不出 a \equiv b \pmod m,除非 c 与 m 互质。要处理除法,就得请出逆元。
裴蜀定理与扩展欧几里得
裴蜀定理:对于不全为零的整数 a、b,存在整数 x、y 使得
ax + by = \gcd(a, b)
也就是说,\gcd(a, b) 是 a 和 b 能线性组合出来的最小正整数。
扩展欧几里得算法不仅求出 \gcd,还顺带求出满足上式的 x 和 y。做法是在辗转相除的回溯过程中,把系数一层层推回去。
// 求 ax + by = gcd(a, b) 的一组解,返回 gcd
long long exgcd(long long a, long long b, long long &x, long long &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
long long d = exgcd(b, a % b, y, x);
y -= a / b * x; // 把上一层的系数调整回来
return d;
}推导思路是:设 a % b = a - \lfloor a/b \rfloor \cdot b,代入下一层的等式,整理后就能得到当前层的 x、y。递归到 b = 0 时,ax = a 的解是 x = 1、y = 0,往回一路上推即可。
模意义下的逆元
如果存在整数 x 使得
a \times x \equiv 1 \pmod m
就称 x 是 a 在模 m 意义下的逆元,记作 a^{-1}。它相当于模意义下的倒数:除以 a 就是乘以 a^{-1}。
逆元存在的充要条件是 \gcd(a, m) = 1。不互质时逆元不存在,除法也就没法进行。
用扩展欧几里得求逆元
要求 a^{-1} \pmod m,等价于解 ax + my = 1。这正是扩展欧几里得的任务。
long long inv(long long a, long long m) {
long long x, y;
exgcd(a, m, x, y); // 解出 ax + my = gcd(a, m)
return (x % m + m) % m; // 化成 [0, m) 范围内的正整数
}这个方法对任意满足 \gcd(a, m) = 1 的 m 都适用。
用费马小定理求逆元
费马小定理:若 p 是质数,且 a 不是 p 的倍数,则
a^{p-1} \equiv 1 \pmod p
两边同时乘 a^{-1},得到
a^{-1} \equiv a^{p-2} \pmod p
所以在模质数 p 的情况下,a 的逆元就是 a^{p-2},用快速幂 O(\log p) 就能求出来。
const long long MOD = 1000000007; // 一个大质数
long long inv(long long a) {
return fastPow(a, MOD - 2, MOD);
}题面里常见的 10^9+7 和 998244353 都是质数,用这个式子最方便。
欧拉定理与欧拉函数
费马小定理是欧拉定理的特例。欧拉函数 \varphi(n) 表示 1 到 n 中与 n 互质的数的个数。
若 \gcd(a, n) = 1,则
a^{\varphi(n)} \equiv 1 \pmod n
欧拉函数的计算式来自唯一分解定理。若 n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k},则
\varphi(n) = n \prod_{i=1}^{k} \left(1 - \frac{1}{p_i}\right)
单个数的欧拉函数可以在质因数分解的过程中顺手算出来:
long long phi(long long n) {
long long res = n;
for (long long i = 2; i * i <= n; i++) {
if (n % i == 0) {
res = res / i * (i - 1); // 先除后乘,避免溢出
while (n % i == 0) n /= i;
}
}
if (n > 1) res = res / n * (n - 1);
return res;
}几个常用值:\varphi(p) = p - 1(p 为质数),\varphi(1) = 1,\varphi(p^k) = p^k - p^{k-1}。
中国剩余定理
中国剩余定理(CRT)解决的是「一个数被几个数除的余数都已知,求这个数」:
\begin{cases}
x \equiv a_1 \pmod{m_1} \\
x \equiv a_2 \pmod{m_2} \\
\vdots \\
x \equiv a_k \pmod{m_k}
\end{cases}
当模数 m_1, m_2, \dots, m_k 两两互质时,在模 M = m_1 m_2 \cdots m_k 的意义下有唯一解。
构造方法:令 M_i = M / m_i,求出 M_i 在模 m_i 下的逆元 t_i,则
x = \sum_{i=1}^{k} a_i M_i t_i \pmod M
记住适用条件就行:模数必须两两互质。不互质时要用扩展中国剩余定理(EXCRT),属于更进阶的内容。
威尔逊定理
p 是质数当且仅当
(p-1)! \equiv -1 \pmod p
这个定理把质数判断和阶乘联系了起来,考试里多以「下列哪个式子等价于 p 是质数」的形式出现。实际编程中很少用它判断质数,因为算阶乘比试除慢得多。
组合数取模
初等数论里求 C_n^m 用的是杨辉三角递推,O(n^2),n 到 10^3 还行,再大就顶不住。模数为质数 p 时,可以用阶乘和逆元把单次查询降到 O(1)(预处理 O(n))。
C_n^m = \frac{n!}{m!(n-m)!} = n! \times (m!)^{-1} \times ((n-m)!)^{-1}
const long long MOD = 1000000007;
const int MAXN = 1000005;
long long fact[MAXN], invFact[MAXN];
void init() {
fact[0] = 1;
for (int i = 1; i < MAXN; i++) fact[i] = fact[i-1] * i % MOD;
invFact[MAXN - 1] = fastPow(fact[MAXN - 1], MOD - 2, MOD); // 一次快速幂
for (int i = MAXN - 2; i >= 0; i--) invFact[i] = invFact[i+1] * (i + 1) % MOD;
}
long long C(int n, int m) {
if (m < 0 || m > n) return 0;
return fact[n] * invFact[m] % MOD * invFact[n-m] % MOD;
}只需求出最大的那个阶乘的逆元,其余逆元可以倒着递推出来,省下大量快速幂。
初赛选择题精选
数论进阶是 CSP-S 笔试的常客。下面 8 道题按考点分类编写,覆盖逆元、费马小定理、欧拉函数与欧拉定理、中国剩余定理、威尔逊定理、裴蜀定理与逆元唯一性这些高频考点。先自己做,再看答案与解析。
题 1(逆元存在性)
下列哪个数在模 12 的意义下存在乘法逆元?
A. 4 B. 6 C. 8 D. 5
答案:D
解析:逆元存在的充要条件是与模数互质。\gcd(5, 12) = 1,而 4、6、8 与 12 的最大公约数分别是 4、6、4,都不互质,逆元不存在。
题 2(费马小定理求逆元)
3 在模 7 意义下的逆元是多少?
A. 3 B. 4 C. 5 D. 6
答案:C
解析:模数 7 是质数,用费马小定理:3^{-1} \equiv 3^{7-2} = 3^5 = 243 \equiv 5 \pmod 7。验证:3 \times 5 = 15 = 2 \times 7 + 1 \equiv 1 \pmod 7,正确。
题 3(欧拉函数)
欧拉函数 \varphi(12) 的值是( )。
A. 4 B. 6 C. 8 D. 11
答案:A
解析:12 = 2^2 \times 3,代入公式:\varphi(12) = 12 \times (1 - \frac{1}{2}) \times (1 - \frac{1}{3}) = 4。与 12 互质的是 1、5、7、11,正好 4 个。
题 4(中国剩余定理)
满足 x \equiv 2 \pmod 3 且 x \equiv 3 \pmod 5 的最小正整数 x 是( )。
A. 8 B. 13 C. 23 D. 5
答案:A
解析:用 CRT 的构造公式(M = 15)得 x = 8;也可以从小到大验证:8 除以 3 余 2、除以 5 余 3,是最小的解。通解是 8 + 15k。
题 5(威尔逊定理)
由威尔逊定理,6! \bmod 7 的值是( )。
A. 0 B. 1 C. 6 D. 5
答案:C
解析:7 是质数,威尔逊定理给出 (7-1)! = 6! \equiv -1 \pmod 7,而 -1 \bmod 7 = 6。直接算验证:720 = 102 \times 7 + 6,余数正是 6。
题 6(欧拉定理)
若 \gcd(a, n) = 1,则 a^{\varphi(n)} \bmod n 等于( )。
A. 0 B. 1 C. a D. \varphi(n)
答案:B
解析:这正是欧拉定理的内容:若 \gcd(a, n) = 1,则 a^{\varphi(n)} \equiv 1 \pmod n。
特例:当 n 是质数 p 时,\varphi(p) = p - 1,欧拉定理退化成费马小定理 a^{p-1} \equiv 1 \pmod p。费马小定理是欧拉定理的特例,这个包含关系选择题常考。
题 7(扩展欧几里得)
方程 6x + 4y = 1 的整数解的情况是( )。
A. 有无穷多组解 B. 有唯一解 C. 无解 D. 恰有两组解
答案:C
解析:由裴蜀定理,方程 ax + by = c 有整数解的充要条件是 \gcd(a, b) \mid c。
这里 \gcd(6, 4) = 2,而 2 \nmid 1,所以无解。这是裴蜀定理最直接的考法:先算 gcd,再看它能不能整除右边的常数。
反过来,如果 \gcd(a,b) \mid c 成立,那么解有无穷多组(通解是特解加上 (b/g, -a/g) 的整数倍)。
题 8(逆元的唯一性)
在模 7 意义下,3 的逆元是( )。
A. 2 B. 3 C. 5 D. 6
答案:C
解析:逆元 x 要满足 3x \equiv 1 \pmod 7。逐个验证:
3 \times 2 = 6 \equiv 63 \times 3 = 9 \equiv 23 \times 5 = 15 \equiv 1✓3 \times 6 = 18 \equiv 4
所以逆元是 5。
性质:模 p(p 为质数)意义下,除 0 以外每个数都有唯一的逆元,且逆元的逆元是它自己。这里 5 的逆元也是 3(5 \times 3 = 15 \equiv 1),可以验证这个对称性。
练习
练习 1:用扩展欧几里得求逆元
题目描述
给定 a 和 m(保证 \gcd(a, m) = 1),求 a 在模 m 意义下的逆元(0 到 m - 1 之间的那个)。
输入格式
一行两个整数 a 和 m。
输出格式
输出一个整数,表示 a 模 m 的逆元。
数据范围
1 \le a < m \le 10^5,保证\gcd(a, m) = 1。
输入输出样例
输入
3 10输出
7说明:3 \times 7 = 21 \equiv 1 \pmod{10}。
题目分析
正文扩展欧几里得模板的直接落地:解 ax + my = \gcd(a, m) = 1,把 x 调整到 [0, m) 区间就是逆元。
参考代码
练习 2:欧拉函数
题目描述
给定一个正整数 n,求 \varphi(n) 的值。
输入格式
一个整数 n。
输出格式
输出一个整数,表示 \varphi(n)。
数据范围
1 \le n \le 10^9。
输入输出样例
输入
12输出
4题目分析
正文欧拉函数代码的直接落地:质因数分解过程中,每找到一个质因数 p,就把结果乘上 (1 - 1/p),代码里写成先除后乘的 res = res / p * (p - 1)。复杂度 O(\sqrt n),n = 10^9 时约 3 万次运算。
参考代码
练习 3(挑战):同余方程组
题目描述
求最小的非负整数 x,满足:
x \equiv a_1 \pmod{m_1}, \quad x \equiv a_2 \pmod{m_2}
给定两组同余条件,求最小的非负整数解。
输入格式
一行四个整数 a_1、m_1、a_2、m_2。
输出格式
输出一个整数,表示最小的非负解。
数据范围
0 \le a_i < m_i \le 10^5,m_1与m_2互质。
输入输出样例
输入
2 3 3 5输出
8题目分析
这是两个方程的中国剩余定理,按正文公式实现即可:
M = m_1 \times m_2,M_1 = m_2,M_2 = m_1;- 用扩展欧几里得求
M_1模m_1的逆元t_1、M_2模m_2的逆元t_2; - 答案是
x = (a_1 M_1 t_1 + a_2 M_2 t_2) \bmod M。
验证样例:x = 2 \times 5 \times 2 + 3 \times 3 \times 2 = 38 \equiv 8 \pmod{15},而 8 除以 3 余 2、除以 5 余 3,正确。
限制 m_i \le 10^5 是为了让所有中间乘积都装进 long long;模数更大的场合要用 __int128 或专门的乘法取模技巧。
参考代码
常见易错点
- 忘记检查
\gcd(a, m) = 1。不互质时逆元不存在,硬套公式会算出一个没有意义的数。 - 扩展欧几里得递归时
x、y的传递顺序容易写反,写完后代回去验证ax + by = \gcd。 - 求出的逆元可能是负数,要化成
[0, m)范围:(x % m + m) % m。 - 费马小定理的指数是
p-2,不是p-1。a^{p-1} \equiv 1,a^{p-2} \equiv a^{-1}。 - 中国剩余定理要求模数两两互质,条件不满足时不能直接套公式。
- 组合数取模的前提是模数为质数且
n < p。n \ge p时阶乘会变成 0,要用卢卡斯定理。 - 会用扩展欧几里得求逆元,模数为质数时也可以直接用
a^{p-2}。 - 会计算欧拉函数
\varphi(n),会解模数互质的同余方程组(CRT 构造法)。
小结
- 同余式能加减乘,不能随便除;想让除法成立就要用逆元。
- 裴蜀定理说
ax + by = \gcd(a, b)一定有整数解,扩展欧几里得负责找出来。 - 逆元存在当且仅当
\gcd(a, m) = 1,用扩展欧几里得求;模数为质数时也可以直接用a^{p-2}。 - 欧拉定理
a^{\varphi(n)} \equiv 1 \pmod n是费马小定理的推广。 - 中国剩余定理处理模数两两互质的同余方程组。
- 组合数取模用阶乘加逆元,一次预处理,
O(1)查询。