模逆元
本文介绍模意义下乘法运算的逆元，并讨论它的常见求解方法．
基本概念
非零实数 𝑎 ∈𝐑a∈R
的乘法逆元就是它的倒数 𝑎−1a−1．类似地，数论中也可以定义一个整数 𝑎a 在模 𝑚m 意义下的逆元 𝑎−1mod𝑚a−1modm，或简单地记作 𝑎−1a−1．这就是 模逆元 （modular multiplicative inverse），也称作 数论倒数 ．
逆元
对于非零整数 𝑎,𝑚a,m，如果存在 𝑏b 使得 𝑎𝑏 ≡1(mod𝑚)ab≡1(modm)，就称 𝑏b 是 𝑎a 在模 𝑚m 意义下的 逆元 （inverse）．
这相当于说，𝑏b 是线性同余方程 𝑎𝑥 ≡1(mod𝑚)ax≡1(modm) 的解．根据 线性同余方程 的性质可知，当且仅当 gcd(𝑎,𝑚) =1gcd(a,m)=1，即 𝑎,𝑚a,m 互素时，逆元 𝑎−1mod𝑚a−1modm 存在，且在模 𝑚m 的意义下是唯一的．
单个逆元的求法
利用扩展欧几里得算法或快速幂法，可以在 𝑂(log𝑚)O(logm) 时间内求出单个整数的逆元．
扩展欧几里得算法
求解逆元，就相当于求解线性同余方程．因此，可以使用 扩展欧几里得算法 在 𝑂(logmin{𝑎,𝑚})O(logmin{a,m}) 时间内求解逆元．同时，由于逆元对应的线性方程比较特殊，可以适当地简化相应的步骤．
参考实现
C++Python
---|---
---|---
这一算法适用于所有逆元存在的情形．
快速幂法
这一方法主要适用于模数是素数 𝑝p 的情形．此时，由 费马小定理 可知对于任意 𝑎 ⟂𝑝a⟂p 都有
𝑎⋅𝑎𝑝−2=𝑎𝑝−1≡1(mod𝑝).a⋅ap−2=ap−1≡1(modp).
根据逆元的唯一性可知，逆元 𝑎−1mod𝑝a−1modp 就等于 𝑎𝑝−2mod𝑝ap−2modp，因此可以直接使用 快速幂 在 𝑂(log𝑝)O(logp) 时间内计算：
参考实现
C++Python
---|---
---|---
当然，理论上，这一方法可以利用 欧拉定理 推广到一般的模数 𝑚m 的情形，即利用 𝑎𝜑(𝑚)−1mod𝑚aφ(m)−1modm 计算逆元．但是，单次求解 欧拉函数 𝜑(𝑚)φ(m) 并不容易，因此该算法在一般情况下效率不高．
多个逆元的求法
有些场景下，需要快速处理出多个整数 𝑎1,𝑎2,⋯,𝑎𝑛a1,a2,⋯,an 在模 𝑚m 意义下的逆元．此时，逐个求解逆元，总共需要 𝑂(𝑛log𝑚)O(nlogm) 的时间．实际上，如果将它们统一处理，就可以在 𝑂(𝑛 +log𝑚)O(n+logm) 的时间内求出所有整数的逆元．
考虑序列 {𝑎𝑖}{ai} 的前缀积：
𝑆0=1, 𝑆𝑖=𝑎𝑖𝑆𝑖−1, 𝑖=1,2,⋯,𝑛.S0=1, Si=aiSi−1, i=1,2,⋯,n.
只要每个 𝑎𝑖ai 都与 𝑚m 互素，它们的乘积 𝑆𝑛Sn 就与 𝑚m 互素．因此，可以通过前文所述算法求出 𝑆−1𝑛mod𝑚Sn−1modm 的值．因为乘积的逆元就是逆元的乘积，所以，从 𝑆−1𝑛Sn−1 出发，反向遍历序列就能求出每个 𝑆𝑖Si 的逆元：
𝑆−1𝑖−1=𝑎𝑖𝑆−1𝑖mod𝑚, 𝑖=𝑛,𝑛−1,⋯,1.Si−1−1=aiSi−1modm, i=n,n−1,⋯,1.
由此，单个 𝑎𝑖ai 的逆元可以通过下式计算：
𝑎−1𝑖=𝑆𝑖−1𝑆−1𝑖mod𝑚, 𝑖=1,2,⋯,𝑛.ai−1=Si−1Si−1modm, i=1,2,⋯,n.
参考实现如下：
参考实现
C++Python
---|---
---|---
算法中，只求了一次单个元素的逆元，因此总的时间复杂度是 𝑂(𝑛 +log𝑚)O(n+logm) 的．
线性时间预处理逆元
如果要预处理前 𝑛n 个正整数在素数模 𝑝p 下的逆元，还可以通过本节将要讨论的递推关系在 𝑂(𝑛)O(n) 时间内计算．这一方法常用于组合数计算中前 𝑛n 个正整数的阶乘的倒数的预处理．
对于 1 <𝑖 <𝑝1<i<p 的正整数 𝑖i，考察带余除法：
𝑝=⌊𝑝𝑖⌋𝑖+(𝑝mod𝑖).p=⌊pi⌋i+(pmodi).
将该等式对素数 𝑝p 取模，就得到
0≡⌊𝑝𝑖⌋𝑖+(𝑝mod𝑖)(mod𝑝).0≡⌊pi⌋i+(pmodi)(modp).
将等式两边同时乘以 𝑖−1(𝑝mod𝑖)−1i−1(pmodi)−1 就得到
𝑖−1≡−⌊𝑝𝑖⌋(𝑝mod𝑖)−1(mod𝑝).i−1≡−⌊pi⌋(pmodi)−1(modp).
这就是用于线性时间递推求逆元的公式．由于 𝑝mod𝑖 <𝑖pmodi<i，这一公式将求解 𝑖−1mod𝑝i−1modp 的问题转化为规模更小的问题 (𝑝mod𝑖)−1mod𝑝(pmodi)−1modp．因此，从 1−1mod𝑝 =11−1modp=1 开始，对每个 𝑖i 顺次应用该公式，就可以在 𝑂(𝑛)O(n) 时间内获得前 𝑛n 个整数的逆元．
参考实现如下：
参考实现
C++Python
---|---
---|---
这一算法只适用于模数是素数的情形．对于模数 𝑚m 不是素数的情形，无法保证递推公式中得到的 𝑚mod𝑖mmodi 仍然与 𝑚m 互素，因而递推所需要的 (𝑚mod𝑖)−1(mmodi)−1 可能并不存在．一个这样的例子是 𝑚 =8,𝑖 =3m=8,i=3．此时，𝑚mod𝑖 =2mmodi=2，不存在模 𝑚m 的逆元．
另外，得到该递推公式后，一种自然的想法是直接递归求解任意一个数 𝑎a 的逆元．每次递归时，都利用递推公式将它转化为更小的余数 𝑝mod𝑎pmoda 的逆元，直到余数变为 11 时停止．目前尚不清楚这样做的复杂度1，因此，推荐使用前文所述的常规方法求解．
习题
参考资料与注释
- riteme 在知乎上的回答 中指出，这样做理论上已知的复杂度的上界是 𝑂(𝑝1/3+𝜀)O(p1/3+ε)，而在实际随机数据中的表现接近于 𝑂(log𝑝)O(logp)． ↩
本页面最近更新： 2026/1/7 08:56:54，更新历史 发现错误？想一起完善？在 GitHub 上编辑此页！ 本页面贡献者：Ir1d, Xeonacid, Enter-tainer, sshwy, StudyingFather, MegaOwIer, PeterlitsZo, Tiphereth-A, hsfzLZH1, iamtwz, jifbt, Marcythm, ouuan, stevebraveman, abc1763613206, buggg-hfc, c-forrest, Chrogeek, Early0v0, Great-designer, Henry-ZHR, hqztrue, ImpleLee, JellyGoat, ksyx, lhhxxxxx, Menci, MioChyan, n-WN, Phemon, shawlleyw, Siyuan, skr2005, thredreams, Tiooo111, WAAutoMaton, Zhaoyangzhen 本页面的全部内容在CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用