09 快速幂求逆元
学习目标
学完这一节，你应该能够：
- 理解为什么直接计算大指数很慢；
- 理解指数的二进制拆分；
- 理解快速幂中
ans、a、b 每一步分别表示什么；
- 独立写出快速幂模板；
- 使用费马小定理和快速幂求素数模下的逆元。
1. 为什么需要快速幂
上一章得到：
如果 p 是素数，并且 p∤a，那么：
a−1≡ap−2(modp)
所以求逆元的问题变成计算：
ap−2modp
如果：
p≈109
那么指数 p−2 也接近 109。
如果直接循环乘法：
long long ans = 1;
for (long long i = 1; i <= b; i++) {
ans = ans * a % mod;
}
需要大约 b 次乘法。
当 b 很大时会非常慢。
2. 从 a13 开始观察
直接计算：
a13
可以把 13 拆成：
13=8+4+1
所以：
a13=a8⋅a4⋅a
而这些幂可以通过不断平方得到：
a2=a⋅a
a4=(a2)2
a8=(a4)2
所以只要不断平方，就能快速得到：
a, a2, a4, a8, a16,…
这些指数正好是：
1,2,4,8,16,…
3. 为什么这和二进制有关
13 的二进制是：
13=(1101)2
因为：
13=1×8+1×4+0×2+1×1
也就是：
13=8+4+1
所以：
a13=a8⋅a4⋅a
二进制中的某一位是 1，就表示这一位对应的幂需要乘进答案。
因此：
快速幂本质上是在按照指数的二进制位拆分幂。
4. 为什么从最低位开始处理
假设当前指数是 b。
C++ 中：
b & 1
可以判断 b 的二进制最低位是不是 1。
如果最低位是 1，就把当前的 a 乘进答案：
if (b & 1) {
ans = ans * a % mod;
}
第一轮的 a 表示原来的：
a1
所以最低位为 1 时，就意味着指数中需要这一份 a1。
5. 为什么每轮都要让底数平方
处理完当前最低位以后，下一位对应的指数权值会翻倍。
依次对应：
1,2,4,8,…
所以当前底数也应该依次表示：
a1,a2,a4,a8,…
因此每一轮都做：
a = a * a % mod;
这样：
- 第一轮的
a 表示 a1；
- 第二轮的
a 表示 a2；
- 第三轮的
a 表示 a4；
- 第四轮的
a 表示 a8。
每一步都取模，是因为同余的乘法性质保证：
(xmodm)(ymodm)modm
和：
xymodm
得到相同的模 m 结果。
6. 为什么每轮都让指数右移
处理完当前最低位后，这一位就不需要再处理。
例如：
13=(1101)2
删除最低位的 1 后，剩下：
(110)2
也就是：
6
C++ 中：
b >>= 1;
对于非负整数，相当于：
b /= 2;
例如：
13→6→3→1→0
当：
b=0
时，所有二进制位都已经处理完。
7. 手推一次 313mod7
初始：
ans=1,a=3,b=13
第 1 轮
b=13
13 是奇数，所以最低位为 1。
把当前 a 乘进答案：
ans=1×3mod7=3
底数平方：
a=32mod7=2
指数右移：
b=13/2=6
所以：
ans=3,a=2,b=6
第 2 轮
b=6
6 是偶数，所以最低位为 0，不乘进答案：
ans=3
底数平方：
a=22mod7=4
指数右移：
b=6/2=3
所以：
ans=3,a=4,b=3
第 3 轮
b=3
最低位为 1：
ans=3×4mod7=5
底数平方：
a=42mod7=2
指数右移：
b=3/2=1
所以：
ans=5,a=2,b=1
第 4 轮
b=1
最低位为 1：
ans=5×2mod7=3
按照代码，底数仍然继续平方：
a=22mod7=4
然后指数右移：
b=1/2=0
循环结束。
因此：
313≡3(mod7)
8. 快速幂模板
long long qpow(long long a, long long b, long long mod) {
long long ans = 1;
a = (a % mod + mod) % mod;
while (b > 0) {
if (b & 1) {
ans = ans * a % mod;
}
a = a * a % mod;
b >>= 1;
}
return ans;
}
9. 代码每一行在做什么
long long ans = 1;
因为 1 是乘法单位元，所以答案从 1 开始。
a = (a % mod + mod) % mod;
先把底数调整到：
0≤a<mod
的标准非负余数范围内。
if (b & 1)
检查当前指数的二进制最低位是否为 1。
ans = ans * a % mod;
如果这一位为 1，就把当前这一份幂乘进答案。
a = a * a % mod;
准备下一位对应的：
a2,a4,a8,…
b >>= 1;
删除已经处理过的最低二进制位。
10. 为什么复杂度是 O(logb)
每一轮都会让：
b→⌊2b⌋
也就是指数每次大约缩小一半。
例如：
1000→500→250→125→⋯
经过大约 log2b 轮后就会变成 0。
所以：
O(logb)
11. 用快速幂求逆元
费马小定理已经给出：
如果 p 是素数，并且 p∤a，那么：
a−1≡ap−2(modp)
所以：
long long inv(long long a, long long p) {
return qpow(a, p - 2, p);
}
12. 例子：求 3 在模 7 下的逆元
因为：
3−1≡37−2(mod7)
所以只需要计算：
35mod7
调用：
qpow(3, 5, 7)
得到：
5
因此：
3−1≡5(mod7)
13. 和扩展欧几里得算法怎么选
扩展欧几里得算法只要求：
gcd(a,m)=1
模数 m 可以是合数。
费马小定理加快速幂要求：
- 模数 p 是素数；
- p∤a。
如果竞赛中模数是常见素数，例如：
109+7
快速幂求逆元非常常见。
14. 数据类型提醒
上面的模板使用：
long long
如果模数在 109 左右，例如 109+7，两个小于模数的数相乘仍然在 long long 范围内。
如果模数本身接近 long long 的上限，那么：
a * a
可能先溢出，再取模。
这种情况下需要使用更大的中间类型，例如 __int128，不能只靠 % mod 防止乘法前的溢出。
15. 小练习
练习 1
为什么：
13=(1101)2
能推出：
a13=a8a4a
练习 2
快速幂中的：
a = a * a % mod;
在做什么？
练习 3
快速幂中的：
b >>= 1;
在做什么？
练习 4
快速幂的时间复杂度是多少？
16. 答案
练习 1
因为：
13=8+4+1
所以：
a13=a8+4+1=a8a4a
练习 2
让当前底数依次表示：
a1,a2,a4,a8,…
练习 3
删除已经处理过的指数最低二进制位。
练习 4
O(logb)
有帮助，赞一个