线性预处理逆元
1. 从“倒数”说起——为什么要学模逆元?
同学们,你们还记得小学学的倒数吗?一个数 aaa 的倒数是 1a\frac{1}{a}a1,因为 a×1a=1a \times \frac{1}{a} = 1a×a1=1。比如,3 的倒数是 13\frac{1}{3}31,3 乘以它等于 1。
在编程和数学里,我们经常要在模运算中做“除法”。什么是模运算?简单说就是“取余数”。比如,我们想计算 3÷23 \div 23÷2,但要求结果是一个整数,而且是在某个模数 ppp(比如 7)的意义下。这时候,我们就要用模逆元。
生活小例子:假设你有 10 颗糖,要平均分给 3 个朋友,每人分 3 颗,还剩 1 颗。这个“除以 3”在模 10 的世界里可就不一样了。如果模数是 7,那么“除以 3”相当于找到某个数 xxx,使得 3×x3 \times x3×x 除以 7 的余数等于 1。这个 xxx 就是 3 的模逆元。
一个数 aaa 的模逆元(记作 inv[a]\text{inv}[a]inv[a])满足:
a×inv[a]≡1(modp)a \times \text{inv}[a] \equiv 1 \pmod{p}a×inv[a]≡1(modp)
这里“≡\equiv≡”表示两边除以 ppp 的余数相等。比如在模 7 下,3 的逆元是多少?因为 3×5=153 \times 5 = 153×5=15,15 mod 7=115 \bmod 7 = 115mod7=1,所以 inv[3]=5\text{inv}[3] = 5inv[3]=5。
2. 为什么需要“线性预处理”?
在写代码时,我们常常要反复计算很多数的逆元。比如,要算 111 到 100000010000001000000 里每个数的模逆元,如果用费马小定理或扩展欧几里得算法一个一个求,每个数需要 O(logp)O(\log p)O(logp) 时间,总共 O(nlogp)O(n \log p)O(nlogp),当 nnn 和 ppp 都很大时(比如 n=107,p=109+7n=10^7, p=10^9+7n=107,p=109+7),速度就太慢了。
有没有更快的办法?有的!我们可以用一个巧妙的递推公式,用已经算好的较小数的逆元来推出当前数的逆元,这样只需要 O(n)O(n)O(n) 时间就能得到所有逆元。这就是“线性预处理逆元”。
生活类比:就像你提前把 1 到 100 的倒数都打印在一张表上,以后每次需要某个数的倒数,直接查表,不用再重新算。这个“提前算好所有倒数”的过程就是线性预处理。
3. 数学原理与公式推导(附生活化理解)
假设模数 ppp 是一个质数(比如 7、13、998244353 等)。对于任意整数 iii(1≤i<p1 \le i < p1≤i<p),我们想求 inv[i]\text{inv}[i]inv[i]。
第一步:把 ppp 写成带余除法的形式
p=k×i+r,其中 k=⌊pi⌋, r=p mod ip = k \times i + r, \quad \text{其中 } k = \left\lfloor \frac{p}{i} \right\rfloor,\ r = p \bmod ip=k×i+r,其中 k=⌊ip⌋, r=pmodi
例如,p=7,i=3p=7, i=3p=7,i=3,则 k=2,r=1k = 2, r = 1k=2,r=1,因为 7=2×3+17 = 2\times 3 + 17=2×3+1。
生活理解:想象你有一盘蛋糕(大小 ppp),要分给 iii 个朋友,每人分 kkk 块,最后还剩 rrr 块。这个“剩的” rrr 比 iii 小,所以我们可以用已经算好的逆元来帮忙。
第二步:对等式两边取模 ppp
k×i+r≡0(modp)k \times i + r \equiv 0 \pmod{p}k×i+r≡0(modp)
因为 ppp 本身除以 ppp 余 0,所以左边也等于 0 模 ppp。
第三步:两边同乘 inv[i]×inv[r]\text{inv}[i] \times \text{inv}[r]inv[i]×inv[r]
注意,因为 ppp 是质数,只要 iii 和 rrr 不是 ppp 的倍数,它们的逆元就存在。我们把等式两边都乘以 inv[i]×inv[r]\text{inv}[i] \times \text{inv}[r]inv[i]×inv[r]:
(k×i+r)×inv[i]×inv[r]≡0×inv[i]×invr(k \times i + r) \times \text{inv}[i] \times \text{inv}[r] \equiv 0 \times \text{inv}[i] \times \text{inv}[r] \pmod{p}(k×i+r)×inv[i]×inv[r]≡0×inv[i]×invr
展开左边:
k×i×inv[i]×inv[r]+r×inv[i]×inv[r]k \times i \times \text{inv}[i] \times \text{inv}[r] + r \times \text{inv}[i] \times \text{inv}[r]k×i×inv[i]×inv[r]+r×inv[i]×inv[r]
因为 i×inv[i]≡1i \times \text{inv}[i] \equiv 1i×inv[i]≡1,r×inv[r]≡1r \times \text{inv}[r] \equiv 1r×inv[r]≡1,所以上式变为:
k×1×inv[r]+1×inv[i]≡0k \times 1 \times \text{inv}[r] + 1 \times \text{inv}[i] \equiv 0k×1×inv[r]+1×inv[i]≡0
即:
k×inv[r]+inv[i]≡0k \times \text{inv}[r] + \text{inv}[i] \equiv 0k×inv[r]+inv[i]≡0
第四步:移项,得到递推公式
inv[i]≡−k×invr\text{inv}[i] \equiv -k \times \text{inv}[r] \pmod{p}inv[i]≡−k×invr
在模运算里,负数可以加上 ppp 变成正数。所以常用写法是:
inv[i]=(p−pi×inv[p mod i]) mod p\text{inv}[i] = \left( p - \frac{p}{i} \times \text{inv}[p \bmod i] \right) \bmod pinv[i]=(p−ip×inv[pmodi])modp
这里的 pi\frac{p}{i}ip 是整数除法(向下取整),在代码里用 p / i(C++)或 p // i(Python)。
特别提醒:需要先知道 inv[1]=1\text{inv}[1] = 1inv[1]=1,因为 111 的逆元就是自己。
手工验证例子
取 p=7p=7p=7,计算 inv[1]\text{inv}[1]inv[1] 到 inv[6]\text{inv}[6]inv[6]:
- i=1i=1i=1: inv[1]=1\text{inv}[1] = 1inv[1]=1
- i=2i=2i=2: k=7/2=3k = 7/2 = 3k=7/2=3,r=7%2=1r = 7%2 = 1r=7%2=1,inv[2]=(7−3×inv[1])%7=(7−3)%7=4\text{inv}[2] = (7 - 3 \times \text{inv}[1]) % 7 = (7-3)%7 = 4inv[2]=(7−3×inv[1])%7=(7−3)%7=4。验证:2×4=8≡12\times4=8\equiv12×4=8≡1。
- i=3i=3i=3: k=2,r=1k=2, r=1k=2,r=1,inv[3]=(7−2×1)%7=5\text{inv}[3] = (7 - 2\times1)%7 = 5inv[3]=(7−2×1)%7=5,验证:3×5=15≡13\times5=15\equiv13×5=15≡1。
- i=4i=4i=4: k=1,r=3k=1, r=3k=1,r=3,inv[4]=(7−1×inv[3])%7=(7−5)%7=2\text{inv}[4] = (7 - 1\times\text{inv}[3])%7 = (7-5)%7 = 2inv[4]=(7−1×inv[3])%7=(7−5)%7=2,验证:4×2=8≡14\times2=8\equiv14×2=8≡1。
- i=5i=5i=5: k=1,r=2k=1, r=2k=1,r=2,inv[5]=(7−1×inv[2])%7=(7−4)%7=3\text{inv}[5] = (7 - 1\times\text{inv}[2])%7 = (7-4)%7 = 3inv[5]=(7−1×inv[2])%7=(7−4)%7=3,验证:5×3=15≡15\times3=15\equiv15×3=15≡1。
- i=6i=6i=6: k=1,r=1k=1, r=1k=1,r=1,inv[6]=(7−1×1)%7=6\text{inv}[6] = (7 - 1\times1)%7 = 6inv[6]=(7−1×1)%7=6,验证:6×6=36≡16\times6=36\equiv16×6=36≡1。
全部正确!这个递推公式就像多米诺骨牌一样,从 inv[1]\text{inv}[1]inv[1] 开始,一个个往后推。
4. 编程实现——把公式变成代码
4.1 C++ 实现
#include <iostream>
#include <vector>
using namespace std;
// 线性预处理求 1 到 n 模 p 的逆元,p 必须是质数
vector<int> linear_inv(int n, int p) {
vector<int> inv(n + 1); // 索引从1开始,多开一个位置方便使用
inv[1] = 1; // 1的逆元永远是1
for (int i = 2; i <= n; ++i) {
// 递推公式:inv[i] = p - (p / i) * inv[p % i] % p
// 注意先取模再取负,最后再模p确保非负
inv[i] = (long long)(p - (p / i)) * inv[p % i] % p;
// 另一种写法:inv[i] = (p - (p / i) * inv[p % i] % p) % p;
}
return inv;
}
int main() {
int n = 10, p = 13; // 测试:模13,求1..10的逆元
vector<int> inv = linear_inv(n, p);
for (int i = 1; i <= n; ++i) {
cout << "inv[" << i << "] = " << inv[i] << endl;
}
// 验证:i * inv[i] % p 应该等于1
cout << "\n验证:" << endl;
for (int i = 1; i <= n; ++i) {
cout << i << " * " << inv[i] << " % " << p << " = "
<< (long long)i * inv[i] % p << endl;
}
return 0;
}
代码说明:
- 使用
vector<int>存储结果,下标从1开始。 - 循环从 i=2 到 n,计算 k=p/ik = p / ik=p/i(整数除法),r=p%ir = p % ir=p%i。
- 注意乘法可能溢出,所以用
(long long)强转。 - 公式中
p - (p/i)相当于 −(p/i)- (p/i)−(p/i) 模 ppp,然后再乘以 inv[r]\text{inv}[r]inv[r],最后再取模。
4.2 Python 实现
def linear_inv(n: int, p: int) -> list:
"""
线性预处理求 1 到 n 模 p 的逆元(p为质数)
返回一个列表,索引从0开始,但0号元素无用,1到n存放结果
"""
inv = [0] * (n + 1) # 多开一个位置,inv[0]无意义
inv[1] = 1 # 1的逆元是1
for i in range(2, n + 1):
# 递推公式:inv[i] = p - (p // i) * inv[p % i] % p
# Python中负数的模会自动转为正数,但为了清晰,我们手动处理
inv[i] = (p - (p // i) * inv[p % i] % p) % p
return inv
# 测试
n = 10
p = 13
inv = linear_inv(n, p)
for i in range(1, n + 1):
print(f"inv[{i}] = {inv[i]}")
# 验证
print("\n验证:")
for i in range(1, n + 1):
print(f"{i} * {inv[i]} % {p} = {(i * inv[i]) % p}")
代码说明:
- 与C++类似,先初始化一个长度为 n+1 的列表。
- Python 整数除法用
//。 - 公式中
(p - (p // i) * inv[p % i] % p) % p保证了结果在 000 到 p−1p-1p−1 之间。 - 也可以写成
(- (p//i) * inv[p%i]) % p,因为Python的%会返回非负余数。
5. 新手容易犯的错误(避坑指南)
- 忘记初始化
inv[1] = 1递推公式必须从 i=2i=2i=2 开始,如果inv[1]没有设好,后面的结果全部会错。 - 循环从 i=1 开始或 i=0 开始 应该从
i=2开始,因为 i=1i=1i=1 已经特殊处理。如果从i=1开始,p/1=pp/1 = pp/1=p,p%1=0p % 1 = 0p%1=0,而inv[0]没有定义或根本不存在。 - 忘记取模导致负数 在 C++ 中,
-k * inv[r]可能是负数,一定要加上p并取模。正确写法是(p - (p/i) * inv[p%i] % p) % p或者( (p - (p/i)) * inv[p%i] ) % p。 - 误以为所有数都有逆元 对于非质数模,有些数可能没有逆元(比如 iii 和 ppp 不互质)。本递推公式只适用于质数 ppp,且要求 i<pi < pi<p,因为当 iii 是 ppp 的倍数时不存在逆元。
- 整数除法混淆 在 C++ 中,
p/i是整数除法,但在 Python 中要用p // i。如果用/会得到浮点数,导致错误。
6. 时间复杂度与空间复杂度
- 时间复杂度:O(n)O(n)O(n),只需要一个从 2 到 n 的循环。
- 空间复杂度:O(n)O(n)O(n),需要存储 n+1 个整数。
相比单个逆元计算(O(logp)O(\log p)O(logp)),当 nnn 很大(比如 10710^7107)且 ppp 也很大(如 109+710^9+7109+7)时,线性预处理能省下大量时间。这就像你一次性购买一大堆零食比每次只买一包更有效率。
7. 应用场景举例(生活化)
- 组合数取模:计算 C(n,k) mod pC(n, k) \bmod pC(n,k)modp 时,需要大量阶乘和阶乘的逆元。先用线性预处理求出 1 到 n 每个数的逆元,再乘起来得到阶乘的逆元。比如,你想知道从 10 个同学中选 3 个参加比赛,有多少种选法(结果模 13),就可以用逆元快速计算。
- 分数取模:计算 ab mod p\frac{a}{b} \bmod pbamodp 相当于 a×inv[b] mod pa \times \text{inv}[b] \bmod pa×inv[b]modp。比如,你要平分 10 块饼干给 7 个朋友,每个朋友能分到多少“模概念”下的数量?用逆元就能算。
- 密码学和哈希:在 RSA 加密算法中,需要大量模逆元运算;在哈希表的设计中也会用到。
8. 完整示例:计算 1 到 10 的逆元并验证
我们已经在上面的代码中给出了完整示例。你可以自己运行一下,看看输出结果是否满足 i×inv[i] mod p=1i \times \text{inv}[i] \bmod p = 1i×inv[i]modp=1。
9. 相关指引
线性预处理逆元是模运算中的经典技巧,它和下面这些知识紧密相关:
- 费马小定理:ap−1≡1(modp)a^{p-1} \equiv 1 \pmod{p}ap−1≡1(modp),可用于单个逆元计算(inv[a]=ap−2 mod p\text{inv}[a] = a^{p-2} \bmod pinv[a]=ap−2modp)。
- 扩展欧几里得算法:可以求解 ax+py=1ax + py = 1ax+py=1,得到 xxx 就是逆元。
- 阶乘逆元:有了 1 到 n 的逆元,可以进一步线性求出阶乘的逆元,用于组合数计算。
- 模运算的四则运算:加减乘除在模意义下的规则。
如果你以后遇到“需要频繁求逆元”的问题(比如在组合数学、数论、算法竞赛中),线性预处理就是你的首选工具。记住:公式记牢,代码写好,逆元就能秒速拿到手!
课后小挑战: 请用线性预处理方法,计算模 p=998244353p=998244353p=998244353 下 1 到 1000000 的所有逆元,并验证前几个是否正确。(提示:验证时可以用费马小定理计算单个逆元来对比)
记住:数学是编程的好朋友,把公式理解了,代码自然就会写。加油!