第 81 章 快速幂与逆元¶
配套例题：BISHI64 【模板】快速幂Ⅰ ‖ 模小整数、BISHI65 【模板】分数取模、 BISHI74 【模板】非质模数下的乘法逆元 来源：S3 day6
pow.cpp；day9《数论》（rxz）第 64–73 页「除法 / 逆元」、逆元.cpp； day9 resource《数论与信息学竞赛》（胡渊鸣）第 15–17 页、《数论》（邹雨恒）第 15–20 页、 《数论》（李有为）第 13–15 页；day10《NOIP 组合数学、数论选讲》 前置：80-数论基础、46-位运算
rxz 的课件用了整整十页铺垫「模意义下的除法」这件事：
为什么我迟迟不讲模意义下的除法呢？想一想，有理数允许分数的存在，模意义下还允许吗？ \((5/3)\times 12\)，尽管开始出现了分数（这是不被允许的），但是后来乘上 12， 结果仍然是正整数，因此这个式子在模意义下是合法的。这个问题如何解决呢？
答案是乘法逆元：在模意义下，「除以 \(b\)」被重新定义为「乘以 \(b^{-1}\)」。 而求逆元最常用的手段又是快速幂。这两件事因此绑在一起讲。
本章的 Python 核心结论，一句话：
模幂用内置
pow(a, b, m)，逆元用pow(a, -1, m)。一行都不要手写。
81.1 快速幂¶
原理：指数的二进制拆分¶
要算 \(a^b\)，把 \(b\) 写成二进制 \(b = \sum_i c_i 2^i\)（\(c_i \in \{0,1\}\)）：
而 \(a^{2^0}, a^{2^1}, a^{2^2}, \ldots\) 可以逐次平方得到。于是只要 \(O(\log b)\) 次乘法。
S3 day6 的 pow.cpp 是递归写法：
int pow(int x,int p)
{
if(p==0) return 1;
if(p==1) return x;
int a=pow(x,p/2);
if(p%2==0) return a*a;
else return a*a*x;
}
对应的迭代版（教学用，实战请看 81.2）：
# [片段] 教学用手写快速幂 —— 理解原理即可，实战一律用内置 pow
def qpow(a, b, m):
"""a^b mod m，O(log b) 次模乘。"""
res = 1
a %= m
while b:
if b & 1: # 当前二进制位是 1，累乘进答案
res = res * a % m
a = a * a % m # a 自乘，对应下一个二进制位
b >>= 1
return res % m # ★ 最后再模一次，处理 m == 1 的退化情况
m == 1是快速幂最经典的坑：模 1 意义下一切都是 0， 但res初始化成 1、且 \(b=0\) 时循环一次都不进，会错误返回 1。 上面代码最后那个% m就是在补这个洞。内置pow没有这个问题：pow(1, 0, 1) == 0。
快速幂的推广¶
快速幂的本质是「结合律 + 二分」，所以凡是满足结合律的运算都能这么加速：
| 运算 | 快速幂形式 | 用途 |
|---|---|---|
| 整数乘法 | \(a^b \bmod m\) | 本章 |
| 矩阵乘法 | \(A^n\) | 线性递推加速（85 章） |
| 加法（快速乘） | \(a \times b\) 用加法实现 | C++ 防溢出，见 81.3 |
| 置换的复合 | 置换的 \(k\) 次幂 | 求循环节 |
| \(\min\)/\(\max\)-plus 矩阵 | 最短路的 \(k\) 步转移 | 图论 |
81.2 Python 取舍：内置 pow 不可替代¶
CPython 的三参数 pow(a, b, m) 是纯 C 实现的模幂，对大指数还会自动切换到
5 位滑动窗口算法（比朴素二进制拆分少约 20% 的乘法）。
实测对比（Python 3.9，\(10^5\) 次调用，\(a \le 10^9\)，\(b \sim 10^{18}\)，\(m = 10^9+7\)）：
| 写法 | 耗时 | 相对 |
|---|---|---|
pow(a, b, m)（内置） |
0.37 s | 1× |
| 手写迭代快速幂 | 0.82 s | 2.2× |
手写递归快速幂（直译 pow.cpp） |
1.13 s | 3.0× |
差距看起来「只有」2–3 倍，但请注意：\(T = 2\times10^5\) 组的模板题里， 这就是 0.4 秒和 1.2 秒的区别，加上 IO 与解析开销，足以决定 AC 还是 TLE。
而真正的数量级差距在另一个地方——千万不要写 a ** b % m：
实测（\(b \sim 10^5\)，200 次调用）：
| 写法 | 耗时 |
|---|---|
pow(a, b, m) |
< 0.001 s |
(a ** b) % m |
15.7 s |
差了 5 个数量级。原因很简单：\(a^b\) 有约 \(b\log_{10}a \approx 9\times10^5\) 位， 光是把它算出来就要做几十万次大整数乘法，最后那次取模还是 \(O(d^2)\) 的。 \(b\) 再大一点直接爆内存。
这是 Python 大整数「不溢出」这个优点的阴暗面： C++ 写
a ** b % m会立刻溢出得到垃圾值，你马上就会发现错了； Python 会老老实实地把它算出来，然后卡死。 参见 22-高精度与大整数。
pow 的三个使用注意：
| 情况 | 行为 |
|---|---|
pow(a, b, m)，b >= 0 |
正常模幂，结果在 \([0, m)\) |
pow(a, -1, m) |
求逆元（3.8+），要求 \(\gcd(a,m)=1\)，否则 ValueError |
pow(a, -k, m) |
\(= (a^{-1})^k\)，同样要求互质 |
pow(a, b, 0) |
ValueError: pow() 3rd argument cannot be 0 |
a 为负 |
自动先 a % m，结果仍非负 |
81.3 快速乘：一个 Python 用不上的模板¶
C++ 里当模数 \(m\) 达到 \(10^{18}\) 时，a * b % m 会溢出 long long
（\(10^{18} \times 10^{18} = 10^{36}\)，远超 \(9.2\times10^{18}\)）。
周尚彦的课件专门提了这个问题：
快速乘法：给定 \(a, b, m \le 10^{18}\)，求 \(a \times b \bmod m\)。
C++ 的解法有三种：__int128、「龟速乘」（把乘法拆成 \(O(\log b)\) 次加法，
和快速幂同一个套路）、以及基于浮点的 \(O(1)\) 技巧。
Python 完全不需要这些：
因为 int 是任意精度的。\(10^{18}\) 量级的乘法在 CPython 里是 2 个 limb 乘 2 个 limb，
几乎和小整数一样快。
这是 Python 在数论题里最大的一处便宜： 凡是题面写着「模数 \(\le 10^{18}\)」「需要
__int128」「需要龟速乘」的题， Python 选手直接跳过整个模板。 Miller-Rabin、Pollard-Rho 在 C++ 里的一大半代码量都花在防溢出上， Python 版本因此短得多——见 83-整除分块与数论进阶。
但要记住代价：当模数真的是 \(10^{18}\) 时，Python 的每次 a*b%m 也确实比
\(10^9\) 模数下慢一些（多一个 limb），而且 pow(a,b,m) 的常数会随模数位数上升。
实测 128 位模数下内置 pow 与手写快速幂的差距会从 2.2× 缩小到 1.3×——
因为此时瓶颈变成了大整数乘法本身，而不是解释器开销。
81.4 模意义下的除法问题¶
李有为的课件说得最直白：
但是我们少了除法。仔细一想我们只说了整数能对应到 \(0 \ldots b-1\)， 没说有理数能对应到 \(0 \ldots b-1\)。
在模 \(m\) 的世界里，只有加、减、乘是天然封闭的。 除法必须重新定义：「除以 \(b\)」 \(:=\) 「乘以 \(b\) 的乘法逆元」。
定义：若 \(b x \equiv 1 \pmod m\)，称 \(x\) 为 \(b\) 在模 \(m\) 意义下的乘法逆元， 记作 \(b^{-1}\) 或 \(\operatorname{inv}(b)\)。
rxz 课件里的例子：\(4\) 是 \(3\) 在模 \(11\) 意义下的逆元（\(3\times4=12\equiv1\)）； \(2\) 是 \(7\) 在模 \(13\) 意义下的逆元（\(7\times2=14\equiv1\)）。
逆元什么时候存在？¶
rxz 的课件把这个留成了课后习题（「什么时候找不到逆元？」）。答案由裴蜀定理给出：
定理：\(b\) 在模 \(m\) 下有逆元 \(\iff \gcd(b, m) = 1\)。此时逆元在模 \(m\) 下唯一。
证明：\(bx \equiv 1 \pmod m\) 等价于 \(bx + my = 1\) 有整数解。 由裴蜀定理，这等价于 \(\gcd(b,m) \mid 1\)，即 \(\gcd(b,m)=1\)。 唯一性：若 \(bx \equiv bx' \equiv 1\)，由消去律（\(\gcd(b,m)=1\)）得 \(x \equiv x'\)。\(\square\)
两个直接推论：
- 模数 \(P\) 是质数时，\(1, 2, \ldots, P-1\) 全都有逆元（只有 \(0\) 没有）—— 这就是 rxz 课件说的「为什么模质数」；
- 模数不是质数时，只有与 \(m\) 互质的数才有逆元。\(m = 12\) 时 \(2, 3, 4, 6, 8, 9, 10\) 全都没有逆元。
81.5 费马小定理¶
定理（Fermat）：\(P\) 是质数且 \(\gcd(a, P) = 1\)，则 \(a^{P-1} \equiv 1 \pmod P\)。
胡渊鸣课件给的证明非常漂亮，抄录并补全：
小引理：给定模 \(P\) 意义下两两不同余的一组数 \(a_1, \ldots, a_n\)， 对于任意 \(b\) 与 \(P\) 互质，\(a_1b, a_2b, \ldots, a_nb\) 仍然两两不同余。 （由消去律：\(a_ib \equiv a_jb \Rightarrow a_i \equiv a_j\)。）
证明：\(\{1, 2, \ldots, P-1\}\) 显然两两不同余。由于 \(\gcd(a,P)=1\)， 根据小引理 \(\{a, 2a, \ldots, (P-1)a\}\) 也两两不同余， 且每个都不同余于 0（否则 \(P \mid ka\)，而 \(\gcd(a,P)=1\) 推出 \(P \mid k\)，与 \(k < P\) 矛盾）。 所以它在模 \(P\) 意义下一定是 \(\{1, 2, \ldots, P-1\}\) 的一个排列。 两边取乘积： $\(\prod_{k=1}^{P-1}(ka) \equiv \prod_{k=1}^{P-1} k \pmod P\)$ $\((P-1)!\, a^{P-1} \equiv (P-1)! \pmod P\)$ 因 \(\gcd((P-1)!, P) = 1\)，两边消去 \((P-1)!\)，定理得证。\(\square\)
推论（求逆元）：\(a \cdot a^{P-2} = a^{P-1} \equiv 1\)，所以
费马小定理是欧拉定理的特例（\(P\) 是质数时 \(\varphi(P) = P-1\)）， 见 82-欧拉函数与欧拉降幂。
费马小定理的逆命题不成立！\(2^{340} \equiv 1 \pmod{341}\)， 但 \(341 = 11 \times 31\) 是合数。这类数叫伪素数（Carmichael 数更强）。 这正是 Miller-Rabin 要在费马测试基础上加强的原因，见 83-整除分块与数论进阶。
81.6 求逆元的四种方法¶
方法一：费马小定理 + 快速幂（模数为质数）¶
\(O(\log P)\)，一行。质模数题的标准写法。
方法二：扩展欧几里得（模数任意）¶
模数不是质数时费马小定理彻底失效（\(a^{m-2}\) 不再是逆元）。 解 \(ax + my = 1\)：
# [片段] 模板：扩展欧几里得求逆元（任意模数）
def exgcd(a, b):
"""返回 (g, x, y) 满足 a*x + b*y = g = gcd(a,b)。迭代版。"""
old_r, r = a, b
old_s, s = 1, 0
while r:
q = old_r // r
old_r, r = r, old_r - q * r
old_s, s = s, old_s - q * s
return old_r, old_s, (old_r - old_s * a) // b if b else 0
def inv_exgcd(a, m):
"""a 在模 m 下的逆元；不存在返回 -1。"""
old_r, r = a, m
old_s, s = 1, 0
while r:
q = old_r // r
old_r, r = r, old_r - q * r
old_s, s = s, old_s - q * s
if old_r != 1: # gcd(a, m) != 1 -> 逆元不存在
return -1
return old_s % m # ★ 可能是负数，Python 的 % 自动拉回 [0, m)
Python 捷径：
pow(a, -1, m)的边界行为一定要清楚： - \(\gcd(a, m) = 1\)：正常返回 \([0, m)\) 内的逆元，不要求 \(m\) 是质数； - \(\gcd(a, m) > 1\)：抛ValueError: base is not invertible for the given modulus； - \(m = 1\)：返回 0（模 1 下一切同余）。所以在非质模数题里，必须包
正确写法：try/except，否则一组不互质的数据就 RE：
方法三：线性递推求 \(1 \ldots n\) 的全部逆元（\(O(n)\)）¶
胡渊鸣称之为「比较不为人知的一种可以在 \(O(n)\) 时间内完成此任务的莫名其妙的算法」，
邹雨恒的课件给了同样的推导。S3 day9 的 逆元.cpp 就是这段代码。
推导：设 \(P = \lfloor P/i \rfloor \cdot i + (P \bmod i)\)。两边模 \(P\)： $\(0 \equiv \left\lfloor \frac{P}{i} \right\rfloor i + (P \bmod i) \pmod P\)$ $\((P \bmod i) \equiv -\left\lfloor \frac{P}{i} \right\rfloor i \pmod P\)$ 两边同乘 \(i^{-1} (P \bmod i)^{-1}\)： $\(i^{-1} \equiv -\left\lfloor \frac{P}{i} \right\rfloor (P \bmod i)^{-1} \pmod P\)$ 因为 \(P \bmod i < i\)，所以从小到大计算时 \((P \bmod i)^{-1}\) 已经算出来了。\(\square\)
# [片段] 模板：O(n) 递推求 1..n 的全部逆元（P 为质数且 P > n）
def inv_table(n, P):
"""inv[i] 是 i 在模 P 下的逆元，i = 1..n。"""
inv = [0] * (n + 1)
inv[1] = 1
for i in range(2, n + 1):
inv[i] = (P - P // i) * inv[P % i] % P # ★ 用 P - P//i 代替 -P//i，避免负数
return inv
对照 逆元.cpp 的原始 C++（\(p = 11\) 的演示）：
使用前提：\(P\) 必须是质数，且 \(n < P\)（否则会用到 \(P\) 自己的逆元，不存在）。
Python 的现实评估：这是一个 \(n\) 次的纯 Python 循环。 \(n = 10^6\) 约 0.35 秒，\(n = 10^7\) 就要 3.5 秒——比调 \(10^6\) 次
pow(i, P-2, P)（C 层，约 3.4 秒）只快 10 倍，远不如在 C++ 里那么划算。 而且大多数题真正需要的是阶乘逆元，用下面的「倒推法」只要一次pow。
方法四：阶乘逆元倒推（组合数题的标配）¶
利用 \(\frac{1}{(i-1)!} = \frac{i}{i!}\)：
只要一次模幂就能得到全部阶乘逆元。
# [片段] 模板：阶乘表 + 阶乘逆元倒推（组合数取模的标准前置）
def build_fact(n, P):
"""返回 (fact, inv_fact)，下标 0..n。只做一次 pow。O(n)。"""
fact = [1] * (n + 1)
for i in range(2, n + 1):
fact[i] = fact[i - 1] * i % P
inv_fact = [1] * (n + 1)
inv_fact[n] = pow(fact[n], P - 2, P) # ★ 唯一的一次模幂
for i in range(n, 0, -1):
inv_fact[i - 1] = inv_fact[i] * i % P # 1/(i-1)! = i * (1/i!)
return fact, inv_fact
顺带地，\(\operatorname{inv}[i] = \operatorname{invfact}[i] \times \operatorname{fact}[i-1]\)， 所以这张表也能 \(O(1)\) 给出单个数的逆元。
方法五：批量求逆（任意一组数，只用一次模幂）¶
给定 \(a_1, \ldots, a_n\)（都可逆），要求全部逆元。做前缀积，对最后一个求逆，再倒推：
# [片段] 模板：批量求逆（Montgomery trick），n 个数只做一次 pow
def batch_inverse(a, P):
"""返回列表 inv，inv[i] = a[i]^(-1) mod P。要求每个 a[i] 都与 P 互质。"""
n = len(a)
pre = [1] * (n + 1) # pre[i] = a[0]*...*a[i-1]
for i in range(n):
pre[i + 1] = pre[i] * a[i] % P
cur = pow(pre[n], P - 2, P) # ★ 唯一的一次模幂
inv = [0] * n
for i in range(n - 1, -1, -1):
inv[i] = cur * pre[i] % P # 1/a[i] = (1/(a0..ai)) * (a0..a_{i-1})
cur = cur * a[i] % P # 退化到 1/(a0..a_{i-1})
return inv
四种方法的选择表¶
| 方法 | 复杂度 | 前提 | 什么时候用 |
|---|---|---|---|
pow(a, P-2, P) |
\(O(\log P)\) | \(P\) 质数 | 求单个逆元的默认写法 |
pow(a, -1, m) |
\(O(\log m)\) | \(\gcd(a,m)=1\) | 模数非质；要 try/except |
| 手写 exgcd | \(O(\log m)\) | 同上 | 需要区分无解或要通解时 |
线性递推 inv[i] |
\(O(n)\) | \(P\) 质数，\(n<P\) | 要 \(1\ldots n\) 全部逆元；Python 下 \(n \le 10^6\) |
| 阶乘逆元倒推 | \(O(n)\) + 1 次 pow | \(P\) 质数，\(P>n\) | 组合数题必用（84 章） |
| 批量求逆 | \(O(n)\) + 1 次 pow | 每个都可逆 | 一组任意的数要全部求逆 |
81.7 分数取模¶
「求 \(\frac{a}{b} \bmod P\)」这个说法要正确理解：它不是先算浮点 \(a/b\) 再取模， 而是求那个唯一的 \(x \in [0, P)\) 满足 \(bx \equiv a \pmod P\)。
# [片段] 模板：分数取模
P = 10 ** 9 + 7
x = a % P * pow(b, P - 2, P) % P # P 为质数
x = a % P * pow(b, -1, P) % P # 等价写法，且不要求 P 是质数
Python 的一个白捡便宜：\(a\) 是负数时，C++ 要写
((a % P) + P) % P， Python 的%直接给出 \([0,P)\) 内的结果。BISHI65 的 \(a\) 下界是 \(-10^9\)， Python 选手完全不用管这件事。
含分数的整个表达式：先把所有分子乘起来、所有分母乘起来（各自随时取模）， 最后只求一次逆元。不要每一项都求一次逆元。
81.8 例题¶
BISHI64 【模板】快速幂Ⅰ ‖ 模小整数（中等）¶
\(T \le 2\times10^5\) 组，每组给 \(0 \le a, b \le 10^9\)（且 \(a+b>0\)）、\(1 \le p \le 10^9\)， 求 \(a^b \bmod p\)。时限 C/C++ 5 秒、其他语言 10 秒。 题面见 BISHI64 原题（牛客）。
这题在 Python 里的正确答案就是「不要写快速幂」：直接调 pow。
import sys
def main():
data = sys.stdin.buffer.read().split()
t = int(data[0])
out = []
ap = out.append
idx = 1
for _ in range(t):
a = int(data[idx]); b = int(data[idx + 1]); p = int(data[idx + 2])
idx += 3
ap(str(pow(a, b, p))) # 内置三参数 pow = C 实现的快速幂
sys.stdout.write("\n".join(out) + "\n")
main()
三个坑：
- \(p\) 可以等于 1！样例第一行
1 0 1的答案是 0，不是 1。 手写快速幂如果把res初始化成 1 而忘了最后% p，这里就错。 内置pow(1, 0, 1)返回 0，天然正确； - \(a\) 可以为 0（题目只保证 \(a+b>0\)，排除了 \(0^0\)）。
pow(0, b, p)对 \(b\ge1\) 返回 0； - \(T = 2\times10^5\)，逐行
input()会被 IO 拖死，必须sys.stdin.buffer.read().split()+ 一次性join输出。
瓶颈分析：本题真正的耗时不在模幂（\(2\times10^5\) 次 C 层 pow 约 0.7 秒），
而在 \(6\times10^5\) 次 int() 解析。所以 IO 优化比算法优化更重要——
这是 Python 模板题的普遍现象，见
20-输入输出处理。
题解见 solutions/BISHI64.py。
BISHI65 【模板】分数取模（中等）¶
\(t \le 10^4\) 组，每组给 \(-10^9 \le a \le 10^9\)、\(1 \le b \le 10^9\)， 求 \(\frac{a}{b} \bmod P\)，\(P = 10^9+7\)（质数），答案保证在 \([0, P-1]\)。 题面见 BISHI65 原题（牛客）。
\(P\) 是质数且 \(1 \le b \le 10^9 < P\)，所以 \(P \nmid b\)，逆元必然存在。 直接费马小定理：
import sys
P = 1000000007
def main():
data = sys.stdin.buffer.read().split()
t = int(data[0])
out = []
ap = out.append
for i in range(t):
a = int(data[1 + 2 * i]); b = int(data[2 + 2 * i])
# 等价写法：inv = pow(b, -1, P)（3.8+，走扩展欧几里得，不要求 P 是质数）
ap(str(a * pow(b, P - 2, P) % P)) # Python 的 % 天然把负数拉回 [0,P)
sys.stdout.write("\n".join(out) + "\n")
main()
三个坑：
- \(a\) 可能是负数。样例 2 的
-114514 1919810答案是101224601。 Python 的%永远返回非负，一个字符都不用改；C++ 必须补((x%P)+P)%P； - 别真的去算浮点
a / b再取模——那是完全不同的东西； - 不要每组重新写快速幂：\(10^4\) 次 C 层
pow只要 0.03 秒，瓶颈仍然是 IO。
对照检验：\(\frac12 \bmod (10^9+7)\)。 \(2^{-1} = \frac{P+1}{2} = 500000004\)，样例第一行正是它。 一个好用的口诀：模 \(P\) 下 \(\frac12\) 就是 \(\frac{P+1}{2}\)（\(P\) 为奇质数）。
题解见 solutions/BISHI65.py。
BISHI74 【模板】非质模数下的乘法逆元（中等）¶
\(T \le 10^4\) 组，每组给 \(1 \le a < m \le 10^9\)，求 \(a^{-1} \bmod m\)。 数据不保证 \(m\) 为质数！ 题面见 BISHI74 原题（牛客）。
题面那句加粗的提示就是全部考点：费马小定理在这里彻底失效。 \(a^{m-2}\) 一般不是逆元——比如 \(m = 12, a = 5\)，\(5^{10} \bmod 12 = 1\) 纯属巧合， 换成 \(m = 15, a = 2\)，\(2^{13} \bmod 15 = 8\)，而真正的逆元是 \(8\)…… 这种「有时对有时错」比全错更危险，绝不能碰运气。
正解是扩展欧几里得：解 \(ax + my = \gcd(a,m)\)，\(\gcd=1\) 时 \(x \bmod m\) 就是逆元。
import sys
def inv(a, m):
"""扩展欧几里得求 a 在模 m 下的逆元；不存在返回 -1。迭代版，无递归开销。"""
# 维护 old_r = old_s * a + (...) * m，对 (r, s) 做辗转相除
old_r, r = a, m
old_s, s = 1, 0
while r:
q = old_r // r
old_r, r = r, old_r - q * r
old_s, s = s, old_s - q * s
if old_r != 1: # gcd(a, m) != 1 -> 逆元不存在
return -1
return old_s % m # 可能是负数，拉回 [0, m)
def main():
data = sys.stdin.buffer.read().split()
t = int(data[0])
out = []
for i in range(t):
a = int(data[1 + 2 * i]); m = int(data[2 + 2 * i])
# 等价一行写法（Python 3.8+）：
# try: v = pow(a, -1, m)
# except ValueError: v = -1
out.append(str(inv(a, m)))
sys.stdout.write("\n".join(out) + "\n")
main()
四个坑：
- 逆元不存在时输出什么，题面没说。输出描述只写「输出一行一个正整数」， 从措辞看数据应当保证 \(\gcd(a,m)=1\)；本题解在无解时输出 \(-1\)（竞赛最常见约定）， 不影响有解数据的正确性。遇到题面歧义时，选一个不影响合法数据的兜底值；
- exgcd 算出的 \(x\) 可能是负数，必须
% m拉回 \([0, m)\)； - 别写递归 exgcd——\(T=10^4\) 时 \(4.5\times10^5\) 次函数调用开销明显；
- \(m = 1\) 时按惯例逆元记 0，但题目给了 \(a < m\) 所以 \(m \ge 2\)，不会出现。
实战里该怎么写？ 直接用内置：
pow(a, -1, m)内部就是扩展欧几里得，C 实现，比上面的 Python 循环快 3–5 倍。 上面手写一遍是为了讲清原理——模板题的意义在于让你知道内置函数在做什么。
题解见 solutions/BISHI74.py。
81.9 本章速查¶
公式¶
| 名称 | 内容 |
|---|---|
| 快速幂 | \(a^b = \prod_{c_i=1} a^{2^i}\)，\(O(\log b)\) |
| 费马小定理 | \(P\) 质数、\(\gcd(a,P)=1\) \(\Rightarrow\) \(a^{P-1}\equiv1 \pmod P\) |
| 费马求逆 | \(a^{-1} \equiv a^{P-2} \pmod P\) |
| 逆元存在条件 | \(\gcd(a,m)=1\)（裴蜀定理） |
| 线性递推逆元 | \(\operatorname{inv}[i] = (P - \lfloor P/i\rfloor)\cdot \operatorname{inv}[P \bmod i] \bmod P\) |
| 阶乘逆元倒推 | \(\operatorname{invfact}[i-1] = \operatorname{invfact}[i]\cdot i\) |
| 分数取模 | \(\frac ab \equiv a \cdot b^{-1} \pmod P\) |
| \(\frac12 \bmod P\) | \(\frac{P+1}{2}\)（\(P\) 为奇质数） |
Python 取舍¶
| 场景 | 做法 | 理由 |
|---|---|---|
| 模幂 | pow(a, b, m) |
C 实现 + 滑动窗口，比手写快 2–3 倍 |
| 绝对不要 | (a ** b) % m |
大整数膨胀，实测慢 \(10^5\) 倍 |
| 质模数求逆 | pow(a, P - 2, P) |
一行 |
| 任意模数求逆 | pow(a, -1, m) + try/except ValueError |
内部是 exgcd，不要求质模数 |
| 需要判无解 / 求通解 | 手写迭代 exgcd | pow 只抛异常 |
| \(1..n\) 全部逆元 | 线性递推（\(n\le10^6\)） | 纯 Python 循环，\(n\) 大就不划算 |
| 阶乘逆元 | 倒推，只做一次 pow |
组合数题标配 |
| 一组任意数求逆 | 批量求逆（前缀积） | 同样只做一次 pow |
快速乘 / __int128 |
不需要 | Python int 任意精度 |
| 负数取模 | 直接 % |
结果天然非负 |
| \(m = 1\) | 内置 pow 自动返回 0 |
手写快速幂要补最后一次 % m |
陷阱清单¶
| 陷阱 | 后果 |
|---|---|
| 模数可能为 1 | 手写快速幂返回 1 而不是 0 |
| 非质模数用费马小定理 | 偶尔碰巧对，更难查 |
pow(a,-1,m) 未 try |
\(\gcd>1\) 时 ValueError → RE |
| 每项都求一次逆元 | 白白多做 \(n\) 次模幂，应先乘起来最后求一次 |
用 a ** b % m |
大整数爆炸 |
| 递归 exgcd | 大量询问时函数调用开销显著 |