很多人第一次看到“逆元”这个词都会愣一下数论里不是讲过质数、因数、同余了吗怎么突然冒出一个像分数一样的东西其实逆元有个更直白的名字叫“数论倒数”它的作用就是在模运算里帮你做除法。比如你在写代码算到一半发现需要一个中间结果(a / b) % mod麻烦来了——模运算里没有除法。你说那用浮点数除完再取模数据一大就乱套而且题目要的是精确整数余数浮点数一舍入就全毁了。这个时候逆元就是唯一正确答案把“除以 b”变成“乘以 b 的逆元”。这篇文章是“数论从零到数论倒数/逆元”系列的第一篇我准备把逆元从定义到三种常用求法再到实战场景和常见坑位一次性讲透。适合刚开始学数论、准备算法竞赛、或者做密码学相关开发的读者。学完这一篇你会发现逆元不是什么玄学它的来龙去脉非常清晰。1. 为什么模运算里没有除法逆元的定义与存在条件1.1 用一个小例子理解逆元假设模数是 p 7我们要算2 / 3 mod 7。注意这里说的“2 / 3”不是浮点数 0.666...而是指找到某个整数 x使得3 × x ≡ 2 (mod 7)。这个 x 才是真正的“除法结果”。先不要着急算我们换一个更基础的问题3 的逆元是多少就是找某个数 inv[3]使得3 × inv[3] ≡ 1 (mod 7)。逐个试一下3×133×263×39≡23×412≡53×515≡1。找到了inv[3]5。于是2 / 3 mod 7 2 × 5 mod 7 10 mod 7 3验证一下3 × 3 9 ≡ 2 (mod 7)和题意完全吻合。这个例子里藏着一个关键信息模运算的“除法”根本不是把两个数相除而是解一个同余方程。所以逆元本质上是“模 p 乘法群中元素 1 对应的逆元素”它不是四则运算里的倒数而是一个和模数强绑定的整数。1.2 逆元和普通倒数的关系与区别在普通实数域里2 的倒数是 1/2因为它满足 2 × (1/2) 1。模 p 的整数世界里没有分数只有 0 到 p-1 这些整数。我们希望给一个整数 a 找一个“模倒数”x让 a × x 在模 p 下等于 1。这个 x 就是 a 在模 p 下的逆元记作 a^{-1}。不过这里有个坑逆元和模数是绑定的。3 在模 7 下的逆元是 5但在模 11 下3 × 4 12 ≡ 1所以 3 在模 11 下的逆元是 4。同一个数模数一变逆元就变了。你在代码里要是把模数混着用逆元全错而且错得非常隐蔽——因为结果往往还是个合法整数只是答案不对。1.3 什么条件下才存在逆元不是所有整数都有逆元。比如在模 6 下面2 就没有逆元因为 2 乘以任何整数再模 6结果只会是 0、2、4永远到不了 1。逆元存在的充要条件是gcd(a, mod) 1也就是 a 和模数互质。证明也不难。如果 gcd(a, m) d 1那么 ax 永远是 d 的倍数而 ax ≡ 1 (mod m) 意味着 ax - 1 是 m 的倍数左边能被 d 整除右边却是“减去 1”的结果它模 d 等于 -1不可能。反过来如果 gcd(a, m) 1根据裴蜀定理一定存在整数 x、y 使得 ax my 1两边对 m 取模就得到 ax ≡ 1x 就是逆元。这个“反过来”的证明等价于提前预告了后面要讲的扩展欧几里得算法——求逆元本质上就是解这个裴蜀等式。2. 模素数的费马小定理求法快速幂是最短路径2.1 费马小定理说了什么当一个质数 p 和一个不被 p 整除的整数 a 放在一起时会得到一个非常漂亮的结论a^(p-1) ≡ 1 (mod p)直觉上可以这样理解考虑集合 {1, 2, ..., p-1}把每个元素乘以 a 再取模得到的是这个集合的一个重排。因为如果 ax ≡ ay (mod p)那么 a(x-y) 是 p 的倍数a 又不含因子 p只能推出 x ≡ y所以乘法不会把两个不同的数撞到同一个结果。1 到 p-1 的乘积和 (a×1)(a×2)...(a×(p-1)) 在模 p 下相等把两边共同的 (p-1)! 约掉就得到 a^(p-1) ≡ 1。这个证明干净利落也是理解后续公式的最好姿势。2.2 从定理到逆元把 a^(p-1) ≡ 1 两边同时乘以 a^{-1}立刻得到a^(p-2) ≡ a^{-1} (mod p)也就是说当模数 p 是素数时a 的逆元就是 a 的 p-2 次方模 p。不需要解方程不需要递归回溯只要会快速幂一行代码就能拿到逆元。这也是竞赛里最常用、最不容易出错的方法。2.3 快速幂的写法与注意点快速幂的本质是“反复平方法”把指数 b 看作二进制从低位到高位遍历每次决定要不要把当前 a 的平方项乘进结果。代码非常简单def qpow(a, b, mod): res 1 % mod while b: if b 1: res res * a % mod a a * a % mod b 1 return res def mod_inverse(a, p): return qpow(a, p - 2, p)C 的写法也差不多long long qpow(long long a, long long b, long long mod) { long long res 1; while (b 0) { if (b 1) res res * a % mod; a a * a % mod; b 1; } return res; }这里有一个几乎所有新手都会踩的坑乘法取模时要防溢出。如果 mod 接近 1e9两个 1e9 级别的数相乘接近 1e18普通 32 位 int 直接溢出。所以我通常建议统一用 long long 来写 qpow除非你能确定模数很小。要是模数到了 1e18 这个量级long long 也不够得用 __int128 或者拆乘这个我放到最后一节的坑位里细说。2.4 使用费马小定理的边界费马小定理只适用于模数是素数的情况。竞赛里常见的 1e97、998244353 都是素数所以很多人习惯了一上来就qpow(a, mod-2, mod)。但如果模数是合数比如 2024这个式子求出来就不是逆元。记住看到合数模数费马小定理立刻失效改走扩展欧几里得。3. 求解不定方程扩展欧几里得是通用钥匙3.1 扩展欧几里得到底做了什么事普通欧几里得算法用来求最大公因数递归地做a % b直到余数为 0。扩展欧几里得在此基础上多干了一件事求出 gcd(a, b) 的同时还能找到一组整数 x、y使得ax by gcd(a, b)这个不定方程的解不唯一算法只需要返回其中一组。递归回溯时的系数更新公式是 x y1y x1 - (a // b) * y1不需要死记理解“把上一层的解代入下一层的等式”就能随手推出来。3.2 用扩欧求逆元的完整步骤想求 a 在模 m 下的逆元就是解 ax my 1。先调用 exgcd(a, m) 得到 d gcd(a, m) 以及一组 x、y。如果 d 不等于 1说明 a 和 m 不互质逆元不存在如果 d 等于 1那么两边对 m 取模得到 ax ≡ 1x 就是 a 的逆元。注意这里有一个很容易忽略的细节x 可能是负数。比如说求 3 在模 7 下的逆元扩欧很可能给出 x -2而 -2 mod 7 等于 5和费马小定理求出的结果一致。所以拿到 x 后一定要做正数化处理(x % m m) % m。3.3 递归和迭代版本的实现Python 递归版写起来很直观def exgcd(a, b): if b 0: return a, 1, 0 d, x1, y1 exgcd(b, a % b) x y1 y x1 - (a // b) * y1 return d, x, y def mod_inverse(a, m): d, x, y exgcd(a, m) if d ! 1: raise ValueError(inverse doesnt exist) return (x % m m) % mC 用引用传参写法也很干净long long exgcd(long long a, long long b, long long x, long long y) { if (b 0) { x 1; y 0; return a; } long long d exgcd(b, a % b, x, y); long long t x; x y; y t - (a / b) * y; return d; }递归深度的问题也要提一下。虽然 exgcd 的递归次数和欧几里得算法一样平均是 O(log min(a,b))不会太深但在特别极端的模数下仍有栈溢出风险。如果实在不放心可以手写迭代版本不过实战中递归版完全够用。3.4 费马小定理 vs 扩展欧几里得对比项费马小定理 快速幂扩展欧几里得对模数的要求必须是素数任意模数只要 gcd(a,m)1时间复杂度O(log p)O(log a) 级别实现难度需要快速幂逻辑简单需要理解递归回溯典型场景大素数模数、组合数取模RSA解密、非素数模数风险点模数不是素数就全错容易忘记处理负数结果选型建议其实很简单比赛里看到 1e97、998244353 这种素数模数直接用费马小定理做密码学或者模数是个合数就老老实实用扩欧。两个都要会谁也替不了谁。4. O(n) 线性递推批量逆元预处理界的王牌4.1 连续求 1 到 n 所有逆元的需求有时候我们不是求一个逆元而是要把 1 到 n 的逆元全部算出来。比如下一节要讲的组合数预处理需要阶乘数组和阶乘逆元数组本质上的依赖就是连续逆元。如果每个数都用快速幂单独求复杂度是 O(n log p)当 n 到 10^6 还算勉强n 一旦到 10^7超时没跑。线性递推只需要 O(n)这就是它在实战中的价值。4.2 线性递推公式的推导过程这个递推公式第一次看到会觉得是天上掉下来的其实推导非常朴素。设模数 p 为素数我们要算 1 到 n 的逆元且 n p。对任意 i2 ≤ i ≤ n令k p // ir p % i那么 k * i r p于是有k * i r ≡ 0 (mod p)两边同时乘以 i^{-1} 和 r^{-1}k * r^{-1} i^{-1} ≡ 0 (mod p)移项i^{-1} ≡ -k * r^{-1} ≡ -(p // i) * inv[p % i] (mod p)这就是全部的秘密。注意 r 一定小于 i所以 inv[p % i] 必然在之前已经算好了递推才能一路滚下去。边界条件是 inv[1] 1。4.3 实现和边界条件def compute_inv(n, p): inv [0] * (n 1) inv[1] 1 for i in range(2, n 1): inv[i] (p - p // i) * inv[p % i] % p return inv这里用p - p // i代替了-(p // i)目的是直接把结果变成正的避免在部分语言里负数取模的歧义。C 里写inv[i] (p - p / i) * inv[p % i] % p;完全同理。4.4 阶乘逆元的另一条高效路线除了单独递推每个数逆元更常用的是递推阶乘和阶乘逆元的组合。先计算 1! 到 n!然后只对 fac[n] 做一次费马小定理求逆再往回乘fac [1] * (n 1) for i in range(1, n 1): fac[i] fac[i-1] * i % p inv_fac [1] * (n 1) inv_fac[n] qpow(fac[n], p - 2, p) for i in range(n, 0, -1): inv_fac[i-1] inv_fac[i] * i % p这个做法最精妙的地方在于整个预处理过程只需要一次快速幂剩下的全是 O(n) 的乘法。比赛中无论是组合数问题还是概率期望题用到阶乘取模基本都走这条路很少有人真的去把每个数的逆元都算一遍。5. 逆元到底用在哪组合数取模与模意义分数5.1 组合数取模的完整流程C(n, k) 在 n、k 很大时不能直接算阶乘再取模因为中间结果会爆炸式增长。有了上面的 fac 和 inv_fac组合数就是三数相乘def C(n, k, p, fac, inv_fac): if k 0 or k n: return 0 return fac[n] * inv_fac[k] % p * inv_fac[n-k] % p为什么是三个数相乘因为 C(n, k) n! / (k! * (n-k)!)原本是除法的定义在模运算下改写成 n! 乘 k! 的逆元再乘 (n-k)! 的逆元。每一步乘法都要取模否则数据稍微大一点立刻溢出。这个函数在数论题里出现频率极高我建议直接封装成工具函数每次比赛直接抄。5.2 模意义下的分数很多概率题和期望题答案要求输出模意义下的有理数。比如答案是一个分数 k/n题目会说“输出答案对 998244353 取模”意思是把这个分数翻译成整数。具体做法就是 k * modular_inverse(n, mod) % mod。举个例子从一个袋子里摸球中奖率是 3/8输出它模 998244353 的结果就是 3 * inv(8) % MOD。需要理解的是模运算的世界里没有小数逆元就是“模倒数”它在模世界里扮演的就是 1/8 这个角色。这也是为什么很多人把逆元叫数论倒数因为在模算术中你确实可以把它当成分数来用。5.3 密码学里的 RSA 应用RSA 解密过程中需要计算 d e^{-1} mod φ(n)这里的 e 和 φ(n) 互质。注意 φ(n) 不是素数所以费马小定理在这里完全失效必须用扩展欧几里得求逆元。很多教材用欧拉定理推导公式但工程实现上基本都是扩欧一把梭。这个应用足以说明逆元不是纯做题技巧它是真实加密解密流程里跑的东西。理解了逆元你去看 RSA 的密钥生成代码那些数字就不是凭空蹦出来的了。6. 逆元实战中反复踩到的坑6.1 模数是合数时用费马小定理最常见的错误就是把费马小定理用在合数模数上。比如 mod 9用快速幂算 4 的逆元pow(4, 7, 9)得到 4但真正的逆元是 7因为 4×7 28 ≡ 1 (mod 9)。这个问题一旦出现在正式代码里定位起来非常痛苦因为结果看着是个正常整数只是不正确。我的习惯是动手前先问一句模数到底是不是素数6.2 负数逆元漏处理扩欧返回的 x 经常是负数。如果不做正数化直接拿去参与后续乘法结果会错得莫名其妙而且不好查。处理方式很固定x (x % m m) % m这个操作不复杂但漏掉的人真的不少。我在看别人代码的时候几乎每次都会提醒一遍扩欧求完逆元第一件事就是正数化。6.3 乘法溢出问题在 C/Java 里逆元的计算链上每一步乘法都可能溢出。我之前遇到过一个问题本地跑没问题交到评测机上随机 WA后来一查是中间结果乘爆了 int。统一用 long long 能解决大部分情况但如果模数本身接近 1e18 这种变态级别long long 相乘也会爆这时候要用__int128临时承接积再取模long long mul_mod(long long a, long long b, long long mod) { return (__int128)a * b % mod; }Python 没有溢出问题但运行速度慢比赛里大量调用 qpow 时要注意常数。6.4 逆元不存在的场景当 b 和 mod 不互质时a / b 在模意义下没有定义。有的题目会故意放这种数据你需要提前判断 gcd(b, mod) 1不成立就按题目约定处理可能是输出 -1也可能是跳过这个 case。最怕的就是不判断直接求逆元扩欧返回一个 d ! 1你还没检查拿着错误的 x 继续算结果全错。6.5 禁止浮点数掺和不要试图用 1.0 / b 然后四舍五入替代逆元。模运算世界里浮点数就是毒药精度误差会直接毁掉答案。正确答案永远是整数运算加逆元任何想取巧的做法最后都要回来填坑。还有一个小的经验在做模意义下的实数运算时我习惯在每个乘法和加减法之后都顺手取一次模虽然代码看起来啰嗦一点但能保证中间结果始终在可控范围内出问题时也好打印调试。等代码通过后再考虑合并取模做性能优化这个顺序比“先追求简洁、再排错”要省时间得多。P1 这篇把逆元的定义、三种求法、典型应用和坑位都过了一遍。下一篇我打算顺着欧拉定理往下走看看逆元在更复杂结构里的位置到时候你会发现很多看起来高深的东西底子其实就是今天这些基础运算。