本课时有配套视频讲解，购买后即可观看（永久有效）
同余式与模运算意义下的逆元
一、课上练习
编程练习
（暂无）
二、知识总结
✨ 核心思想
在算法竞赛中，很多问题要求答案对一个大质数 p 取模。加、减、乘运算可以随时取模，但除法不能直接取模。例如 (a / b) % p ≠ (a % p) / (b % p)。
为了在模运算下实现"除法"，我们引入模逆元的概念：如果 b x ≡ 1 (mod p)，则 x 称为 b 在模 p 下的逆元，记为 b^(-1)。此时 (a / b) % p = (a b^(-1)) % p。
✨ 算法原理
同余的基本性质
a ≡ b (mod m)表示 m 整除 (a - b)。- 同余关系对加、减、乘封闭：
(a + b) mod m = ((a mod m) + (b mod m)) mod m(a b) mod m = ((a mod m) (b mod m)) mod m
- 除法不封闭，需要使用逆元。
逆元存在的条件
b 在模 m 下的逆元存在，当且仅当 gcd(b, m) = 1（b 和 m 互质）。
当 m 是质数且 b 不是 m 的倍数时，逆元一定存在。
方法一：费马小定理法
当 p 是质数时，由费马小定理 b^(p-1) ≡ 1 (mod p)，因此：
b^(-1) ≡ b^(p-2) (mod p)用快速幂计算 b^(p-2) mod p 即可。
方法二：扩展欧几里得算法（exGCD）
求解 b x + m y = gcd(b, m)。当 gcd(b, m) = 1 时，解中的 x 就是 b 在模 m 下的逆元。
此方法不要求 m 是质数，只要 gcd(b, m) = 1 即可。
方法三：线性递推
预处理 1~n 所有数的逆元：
inv[1] = 1
inv[i] = -(p / i) * inv[p % i] % p推导：设 p = k i + r（k = p/i, r = p%i），则 k i + r ≡ 0 (mod p)，两边乘 i^(-1) r^(-1) 得 i^(-1) ≡ -k r^(-1) (mod p)。
✨ 代码实现
快速幂 + 费马小定理求逆元
mod_inverse_fermat.cpp
1#include <bits/stdc++.h>
2using namespace std;
3
4typedef long long ll;
5const ll MOD = 1e9 + 7; // 常用质数模数
6
7// 快速幂：计算 base^exp % mod
8ll power(ll base, ll exp, ll mod) {
9 ll result = 1;
10 base %= mod;
11 while (exp > 0) {
12 if (exp & 1) {
13 result = result * base % mod;
14 }
15 base = base * base % mod;
16 exp >>= 1;
17 }
18 return result;
19}
20
21// 费马小定理求逆元：b^(p-2) mod p
22ll mod_inverse(ll b, ll p) {
23 return power(b, p - 2, p);
24}
25
26int main() {
27 ios::sync_with_stdio(false);
28 cin.tie(nullptr);
29
30 ll a, b;
31 cin >> a >> b;
32
33 // 计算 (a / b) % MOD = a * b^(-1) % MOD
34 ll inv_b = mod_inverse(b, MOD);
35 ll ans = a % MOD * inv_b % MOD;
36 cout << ans << "\n";
37
38 return 0;
39}扩展欧几里得算法求逆元
mod_inverse_exgcd.cpp
1#include <bits/stdc++.h>
2using namespace std;
3
4typedef long long ll;
5
6// 扩展欧几里得：求 ax + by = gcd(a, b) 的一组解
7ll exgcd(ll a, ll b, ll &x, ll &y) {
8 if (b == 0) {
9 x = 1;
10 y = 0;
11 return a;
12 }
13 ll x1, y1;
14 ll g = exgcd(b, a % b, x1, y1);
15 x = y1;
16 y = x1 - (a / b) * y1;
17 return g;
18}
19
20// exGCD 求逆元（不要求 m 是质数，只要 gcd(b, m) = 1）
21ll mod_inverse(ll b, ll m) {
22 ll x, y;
23 ll g = exgcd(b, m, x, y);
24 if (g != 1) return -1; // 逆元不存在
25 return (x % m + m) % m; // 确保结果为正
26}
27
28int main() {
29 ios::sync_with_stdio(false);
30 cin.tie(nullptr);
31
32 ll b, m;
33 cin >> b >> m;
34
35 ll inv = mod_inverse(b, m);
36 if (inv == -1) {
37 cout << "逆元不存在\n";
38 } else {
39 cout << inv << "\n";
40 // 验证：b * inv ≡ 1 (mod m)
41 cout << "验证：" << b << " * " << inv << " mod " << m
42 << " = " << (b * inv % m) << "\n";
43 }
44
45 return 0;
46}线性预处理逆元
linear_inverse.cpp
1#include <bits/stdc++.h>
2using namespace std;
3
4typedef long long ll;
5const int MAXN = 1000005;
6const ll MOD = 1e9 + 7;
7
8ll inv[MAXN]; // inv[i] = i 在模 MOD 下的逆元
9
10void precompute_inverse(int n) {
11 inv[1] = 1;
12 for (int i = 2; i <= n; i++) {
13 // 递推公式：inv[i] = -(p/i) * inv[p%i] % p
14 inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
15 }
16}
17
18int main() {
19 int n;
20 cin >> n;
21
22 precompute_inverse(n);
23
24 for (int i = 1; i <= n; i++) {
25 cout << "inv[" << i << "] = " << inv[i] << "\n";
26 }
27
28 return 0;
29}✨ 执行示例
费马小定理法
求 3 在模 7 下的逆元：
3^(7-2) = 3^5 mod 7
3^1 = 3
3^2 = 9 mod 7 = 2
3^4 = 2^2 = 4
3^5 = 3^4 * 3^1 = 4 * 3 = 12 mod 7 = 5验证：3 * 5 = 15 mod 7 = 1。正确。
扩展欧几里得法
求 3 在模 7 下的逆元，即求 3x + 7y = 1：
1exgcd(3, 7):
2 exgcd(7, 3):
3 exgcd(3, 1):
4 exgcd(1, 0): x=1, y=0, g=1
5 x = 0, y = 1 - 3*0 = 1 → (3, 1): x=0, y=1
6 x = 1, y = 0 - 2*1 = -2 → (7, 3): x=1, y=-2
7x = -2, y = 1 - 0*(-2) = 1 → (3, 7): x=-2, y=1x = -2，取模后 (-2 + 7) % 7 = 5。与上面一致。
线性递推法
模 7 下的逆元（前 6 个）：
1inv[1] = 1
2inv[2] = -(7/2) * inv[7%2] = -3 * inv[1] = -3 ≡ 4 (mod 7)
3inv[3] = -(7/3) * inv[7%3] = -2 * inv[1] = -2 ≡ 5 (mod 7)
4inv[4] = -(7/4) * inv[7%4] = -1 * inv[3] = -5 ≡ 2 (mod 7)
5inv[5] = -(7/5) * inv[7%5] = -1 * inv[2] = -4 ≡ 3 (mod 7)
6inv[6] = -(7/6) * inv[7%6] = -1 * inv[1] = -1 ≡ 6 (mod 7)验证：24=8≡1, 35=15≡1, 42=8≡1, 53=15≡1, 6*6=36≡1。全部正确。
✨ 解题步骤详解
- 判断是否需要逆元：当表达式中有除法且需要取模时，必须使用逆元。
- 选择方法：
- 模数 p 是质数 → 费马小定理法（最常用）。
- 模数不一定是质数 → 扩展欧几里得法。
- 需要批量求 1~n 的逆元 → 线性递推法。
- 实现快速幂：费马小定理法依赖快速幂，注意防止溢出（使用 long long）。
- 注意取模后为负数：exGCD 的结果可能为负，需要
(x % m + m) % m。
✨ 常见错误
- 模数不是质数却用费马小定理：费马小定理要求 p 是质数。如果 p 不是质数，必须用 exGCD。
- b 是 p 的倍数：此时逆元不存在，需要提前特判。
- 快速幂中忘记取模：
base * base可能溢出 long long，应及时取模。 - 线性递推公式写错符号：递推公式中有一个负号，用
MOD - MOD/i代替-(MOD/i)来避免负数。 - 组合数取模时遗漏逆元：
C(n,k) mod p = n! inv(k!) inv((n-k)!) mod p，阶乘的逆元也需要预处理。
✨ 算法评价
| 方法 | 时间复杂度 | 适用条件 | 特点 |
|---|---|---|---|
| 费马小定理 | O(log p) | p 是质数 | 最常用，代码简单 |
| 扩展欧几里得 | O(log m) | gcd(b,m)=1 | 不要求质数模 |
| 线性递推 | O(n) | p 是质数 | 批量预处理最快 |
模逆元是数论问题和组合计数问题的基础工具。在几乎所有需要"答案对 10^9+7 取模"的题目中，都需要用到逆元来处理除法。