写代码或者刷算法题的时候如果连续碰到“模一个素数”和“算一个分数”你大概率会被同一个东西卡住——逆元也叫数论倒数。比如要算 5 ÷ 3 mod 7你对着整数除法想半天也得不到一个“正常”答案因为在模 7 的世界里除法根本没有被定义。逆元解决的就是这个问题把除法转换成乘法找一个数 x让 3 乘以 x 之后在模 7 意义下等于 1。找到这个 x5 ÷ 3 就能变成 5 乘 x。就这么一个概念在数论、算法竞赛、密码学的 RSA 里反复出现。这篇文章作为系列 P1我打算从零开始把逆元是什么、怎么求、代码怎么写、新手容易踩哪些坑一次性讲透。适合刚接触数论的竞赛选手、对密码学感兴趣的程序员以及准备复试被数论问到的同学。今天讲的都是最基础也最核心的东西理解透了后面看原根、离散对数、二次剩余都会轻松很多。1. 数论倒数到底在算什么1.1 除法在模世界被卡住了先弄明白一件事模运算里加法、减法、乘法都很自然。7 小时转一圈的钟表上3 点加 5 小时是 1 点这本质上就是 (3 5) mod 7 1。乘法呢可以理解成多次加法比如 3 × 3 9在模 7 下等于 2也没毛病。可一旦碰到除法问题就来了5 ÷ 3 在模 7 下等于多少你要是直接做 5 ÷ 3得到的是 1.666...这是个小数而模 7 的世界里只有 0 到 6 这 7 个整数。就算你把 5 ÷ 3 想成“哪个整数乘以 3 之后等于 5”2 × 3 61 × 3 3试一圈也找不到一个整数能让它模 7 等于 5。换一种思路在实数里除法其实就是乘以这个数的倒数3 的倒数是 1/3因为 3 × (1/3) 1。那么在模 7 的世界里能不能也找一个“倒数”呢也就是说找一个小整数 x使 3 × x ≡ 1 (mod 7)。你挨个试3 × 1 33 × 2 63 × 3 9 ≡ 23 × 4 12 ≡ 53 × 5 15 ≡ 1。找到了x 5。这个 5就是 3 在模 7 意义下的“倒数”也叫乘法逆元。有了它5 ÷ 3 就能写成 5 × 5 25模 7 等于 4。你验证一下4 × 3 12 ≡ 5完全正确。所以逆元的本质就是用乘法去模拟除法让原本没法直接算的“模除法”变得可算。1.2 定义与存在条件不是所有数都有“钥匙”正式一点如果 ax ≡ 1 (mod m)就把 x 称为 a 在模 m 意义下的乘法逆元记作 a⁻¹。注意这个记号不是实数里的倒数但在模意义下它的行为和倒数一模一样a 乘以 a⁻¹ 的结果在模 m 下等于单位元 1。既然跟倒数这么像那第一个要搞清楚的问题就是是不是随便一个数都有逆元答案是不一定。逆元存在的充要条件是 gcd(a, m) 1也就是 a 和模数 m 互质。为什么把 ax ≡ 1 (mod m) 展开等价于存在整数 k使得 ax - km 1。如果 gcd(a, m) d 1那么 d 一定整除 ax也一定整除 km所以 d 必须整除 1这显然不可能。反过来如果 gcd(a, m) 1根据后面要讲的扩展欧几里得定理一定存在整数 x、k 满足 ax - km 1也就是逆元一定存在。所以“有没有逆元”这个问题本质上是“互不互质”的问题。这里有个很重要的推论当模数 m 是素数时1 到 m-1 之间所有整数都和 m 互质也就是说除了 0 和 m 的倍数之外每个数都有逆元。这就是为什么后面大量数论题目默认模数是 1000000007 这种大素数题目敢让你随便做除法就是因为每个非零数的逆元都存在。而一旦模数是合数比如模 4 之下2 就没有逆元你试遍 0、1、2、32 乘以任何数模 4 都只能是 0 或 2永远得不到 1。2. 求逆元的三种主流方法2.1 扩展欧几里得最通用的解法求逆元的第一个方法也是适用范围最广的方法叫扩展欧几里得算法简称 exgcd。大家都学过辗转相除法求 gcd它基于一个恒等式gcd(a, b) gcd(b, a mod b)一直递归到 b 0 时gcd 就是 a。扩展欧几里得在此基础上多算了一样东西它不光求出 gcd(a, b)还能同时找出一组整数 x、y使得 ax by gcd(a, b)。这个式子叫裴蜀定理意思是说两个数的最大公约数一定能写成这两个数的整数线性组合。把 b 换成 m如果 gcd(a, m) 1那 exgcd 返回的就是 ax my 1。把这个式子两边同时模 mmy 这一项直接消失剩下 ax ≡ 1 (mod m)所以 exgcd 返回的 x 就是逆元。举一个具体的例子求 3 在模 7 下的逆元。手动跑一遍7 2 × 3 1 1 7 - 2 × 3把第二个式子写成 3 × (-2) 7 × 1 1所以 x -2。但模 7 意义下-2 ≡ 5所以逆元是 5和前面试出来的结果一致。这里要注意exgcd 算出来的 x 可能是负数这时候一定要“修正”到 [0, m-1] 区间。方法就是 x (x % m m) % m先取模再加模再取模保证结果非负。exgcd 的复杂度是 O(log min(a, m))非常快。它的最大优势是模数不要求是素数只要互质就行所以它是处理合数模场景的底牌。2.2 费马小定理模素数的快速通道如果你确定模数 p 是素数那还有一条更快的路费马小定理。定理说对于素数 p且 gcd(a, p) 1有 a^(p-1) ≡ 1 (mod p)。这个式子可以变形a × a^(p-2) ≡ 1 (mod p)所以 a 的逆元就是 a^(p-2) mod p。只要用快速幂把 a^(p-2) 算出来逆元就拿到了。为什么费马小定理成立我给出一个直观的证明思路。考虑 a、2a、3a、...、(p-1)a 这 p-1 个数模 p 的结果。因为 gcd(a, p) 1每个数都不是 p 的倍数而且任意两个的差也不能被 p 整除所以它们模 p 后恰好是 1 到 p-1 的一个排列。把它们全部乘起来就有 a^(p-1) × (p-1)! ≡ (p-1)! (mod p)两边消去 (p-1)!就得到 a^(p-1) ≡ 1 (mod p)。这个方法在竞赛里用得最多原因很现实题目经常给你一个大素数模数比如 1e97、998244353这时候求逆元就是一行快速幂的事。需要注意的是费马小定理的前提是“p 是素数”只要模数是合数a^(m-2) 很可能不是逆元这一点后面专门讲坑。2.3 欧拉定理把素数的限制放宽费马小定理虽然好用但素数这个前提太苛刻了。如果模数是合数有没有一个更一般的定理有就是欧拉定理。欧拉定理说如果 gcd(a, m) 1那么 a^φ(m) ≡ 1 (mod m)其中 φ(m) 是欧拉函数表示 1 到 m 之间与 m 互质的整数个数。根据欧拉定理a 的逆元就是 a^(φ(m)-1) mod m。当 m 是素数 p 时φ(p) p-1欧拉定理就退化成费马小定理所以费马小定理其实是欧拉定理的特例。用欧拉定理求逆元的关键是算出 φ(m)。如果 m 不大可以暴力枚举统计互质数如果 m 很大一般要先分解质因数再运用公式 φ(m) m × ∏(1 - 1/p_i) 计算。每多一个质因子就乘上一个 (p-1)/p。这个公式在初等数论里很常用但本文 P1 阶段先不展开知道有这么一条通用路线即可。三种方法做个简单选型模数是素数优先费马小定理模数是合数但互质用扩展欧几里得最省事或者用欧拉定理而且 exgcd 还能用来判断逆元是否存在这个别名“万能底牌”不是白叫的。3. 直接能用的代码模板3.1 扩展欧几里得模板先上 C 的 exgcd 模板。代码很短但递归边界、引用传参这两点要记牢。#include bits/stdc.h using namespace std; 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 g exgcd(b, a % b, y, x); y - (a / b) * x; return g; } // 求 a 在模 m 下的逆元若不存在返回 -1 long long inv(long long a, long long m) { long long x, y; long long g exgcd(a, m, x, y); if (g ! 1) return -1; return (x % m m) % m; }递归到 b 0 的时候gcd 是 a此时显然 a × 1 0 × 0 a所以 x 1y 0。回溯的过程稍微有点绕关键是利用下一层的 x、y 来更新当前层的值。模板里直接递归时交换 x、y 的位置再修正 y这是最常见的写法我建议直接背熟。C 里要注意a、m 都可能达到 1e9 量级中途乘法可能溢出 int所以要用 long long。最后的(x % m m) % m这一步是必须的它能保证返回的是非负且小于 m 的逆元。Python 版更符合直觉直接同步返回 gcd 和一组解def exgcd(a, b): if b 0: return a, 1, 0 g, x1, y1 exgcd(b, a % b) return g, y1, x1 - (a // b) * y1 def inv(a, m): g, x, _ exgcd(a, m) if g ! 1: return -1 return (x % m m) % m用法验证inv(3, 7)返回 5inv(2, 4)返回 -1。这一份模板可以直接拿到平时的模运算场景里用。3.2 费马小定理 快速幂模板当模数 p 是大素数时逆元 a^(p-2) mod p核心就是快速幂。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; } // 调用方式p 必须是素数 long long inv_prime_mod(long long a, long long p) { return qpow(a, p - 2, p); }Python 更简单内置pow第三个参数就是模数内部已经是快速幂实现def inv_prime_mod(a, p): return pow(a, p - 2, p)有个细节提醒一下C 里的pow是浮点函数千万别和快速幂混淆我见过不少新手拿pow(a, p-2)去取模结果得到一个完全没有意义的大浮点数然后对着答案怀疑人生。写求逆元的代码老老实实用整型快速幂或者 Python 内置的三参 pow。3.3 从 1 连算到 n 的线性递推求逆元有时候题目要一次性算很多个数的逆元比如预处理 1!、2!、...、n! 的逆元。如果对每个数都跑一次 exgcd 或快速幂复杂度是 O(n log mod)数据一大就容易超时。这时候有个 O(n) 的线性递推公式前提同样是模数 p 为素数。公式是inv[i] -(p // i) * inv[p % i] % p写成防负数的代码就是vectorlong long inv_all(int n, long long p) { vectorlong long inv(n 1); inv[1] 1; for (int i 2; i n; i) { inv[i] (p - p / i) * inv[p % i] % p; } return inv; }这个公式怎么来的设 p (p // i) * i (p % i)两边在模 p 下看就有 p % i ≡ -(p // i) * i (mod p)。两边同时乘以 inv[p % i] × inv[i]得到 inv[i] ≡ -(p // i) * inv[p % i] (mod p)。把负号处理掉就是上面的写法。用 p 7 验证一下inv[1] 1inv[2] (7 - 3) × inv[1] % 7 4inv[3] (7 - 2) × inv[1] % 7 5inv[4] (7 - 1) × inv[3] % 7 6 × 5 % 7 2。你检查2 × 4 8 ≡ 13 × 5 15 ≡ 14 × 2 8 ≡ 1全部正确。有了这个数组后面算组合数取模就非常舒服。4. 实战里逆元的价值4.1 模意义下的分数与除法很多人第一次真正需要逆元是在做概率 DP、期望、递推这类题的时候。比如递推公式是 f[i] f[i-1] / k something所有结果都要对一个素数模取模。这时候你没法真的做小数除法因为取模只对整数有意义。正确做法是把“除以 k”换成“乘以 k 的逆元”。换句话说模意义下分数 a/b 定义为 a × b⁻¹ mod m。只要 b 和模数互质这个分数就有明确的整数取值。举个例子在模 7 下计算 5 / 2。inv(2, 7) 4所以 5 / 2 mod 7 5 × 4 20 ≡ 6。你验证6 × 2 12 ≡ 5完全正确。这个 6 在模 7 的世界里就扮演着“二分之五”的角色。这种操作在普通算术里看起来很奇怪但在模世界里是自洽的。4.2 组合数取模的经典套路再往实战走一步组合数取模大概是逆元出场率最高的地方。C(n, k) n! / (k! × (n-k)!)这里面有除法所以模素数 p 下不能直接算。但是只要预处理阶乘和阶乘的逆元组合数计算就变成了几次乘法。具体套路分三步预处理 fac[i]从 0 循环到 nfac[0] 1fac[i] fac[i-1] × i % p。用费马小定理算 fac[n] 的逆元然后反向递推得到所有阶乘逆元invfac[n] qpow(fac[n], p-2, p)invfac[i-1] invfac[i] × i % p。组合数 C(n, k) fac[n] × invfac[k] × invfac[n-k] % p。这个套路几乎是组合计数题的标配你能在无数题解里看到它。为什么需要反向递推而不是单独算每个阶乘逆元因为单个算是 O(n log p)反向递推只用一次快速幂总体 O(n)这在 n 到 1e6、1e7 的场景下区别很大。如果题目要求多个查询这个预处理的优势更明显。当 n、k 超过模数 p 时上面这个直接算的方法就不对了要用 Lucas 定理那是后面章节的内容但在 P1 阶段先把基础套路练熟。4.3 密码学里的一个小轮子逆元不是竞赛专属技巧它是密码学的地基。最典型的例子就是 RSA 算法里计算私钥 d 的过程。在 RSA 里选取两个大素数 p、qn p × qφ(n) (p-1)(q-1)。然后选一个加密指数 e使得 gcd(e, φ(n)) 1。解密指数 d 必须满足 ed ≡ 1 (mod φ(n))。这个 d 就是 e 在模 φ(n) 下的逆元求解方法正是扩展欧几里得算法。可以说没有模逆元RSA 的密钥生成逻辑就崩了。另外在一些哈希函数、伪随机数生成器、有限域运算的设计里也会用到模逆元来构造可逆映射。因为逆元保证“乘以一个数再乘以它的逆元”最后能回到原来的数这种可逆性在设计双向一致性的计算中非常宝贵。对初学者来说知道“逆元是密码学的基础零件之一”就够了真正深入可以在密码学课程里继续展开。5. 新手翻车现场常见问题与排查5.1 逆元不存在时的判断和替代方案最常遇到的翻车场景是模数是合数某个数根本没有逆元。典型例子求 2 在模 4 下的逆元你会发现 2 × 0 02 × 1 22 × 2 02 × 3 2永远得不到 1所以无解。用 exgcd 求逆元时返回的 gcd 不是 1 就说明无解这一点写完模板之后一定别丢。那无解怎么办看题目是否允许换一种方式比如把整条递推式稍微化简或者换一个大素数模数。如果题目设计没问题逆元一般都会被保证存在但作为写代码的人防御性检查很有必要不要一上来就除。5.2 负数取模的语言差异exgcd 返回的 x 经常是负数比如求 3 模 7 的逆元原始 exgcd 给出 x -2。如果不修正在 C 里直接 return -2你拿着去算 5 × (-2) mod 7结果可能变成 -3虽然 (5 × (-2)) mod 7 在数学上等价于 4但取模运算在 C 里对负数的结果也是负数很容易出锅。Python 倒是不一样负数取模会返回非负结果-2 % 7 等于 5所以习惯 Python 的选手可能不会意识到这个问题一旦切到 C 就容易栽。统一的处理方法是 (x % m m) % m把可能为负的 x 调到 [0, m-1] 区间。这个修正对任何语言都适用建议封装进 inv 函数里。5.3 乘法溢出与超大模数的处理当模数 p 是 1e97int 最多到大概 21 亿p × p 已经超过 int 上限所以代码里 a × a % mod 这行a 和 a 相乘可能直接溢出变成负数。C 里解决办法是全部用 long long 存中间变量。当 p 本身达到 1e18 级别long long 相乘也会溢出这时候就要用更高级的手段比如基于二进制分解的快速乘或者直接用__int128临时存中间结果。竞赛里一般用不上但一旦遇到知道有这么回事就能少走弯路。5.4 费马小定理的误用场景把 a^(m-2) mod m 当逆元用前提是 m 为素数。如果 m 是合数费马小定理不成立结果基本是错的。我见过有人用 m 15a 2 去测直接得出一个“看起来像模运算的数”结果完全对不上然后开始怀疑自己代码写错了。实际处理时先确认题目里的模数是不是素数。如果是类似 1e97、998244353 这类基本可以确定是素数放心用费马小定理。如果不是就用 exgcd 判断并求逆元千万不要把一个合数当成素数开 floyd 式骚操作。下面把几个常见问题整理成表常见问题原因解决办法逆元返回负数exgcd 解出来的 x 可能为负统一做 (x % m m) % mgcd 不为 1a 和 m 不互质逆元不存在换互质的模数或换计算方式费马小定理算错模数不是素数误用 a^(p-2)用 exgcd 或欧拉定理乘法溢出a × a 超过 int/long long 范围中间量用 long long必要时 __int128批量逆元太慢每个数单独快速幂用 inv[i] 递推 O(n) 求全部最后再分享一个我自己的小经验。我当年学逆元是在做一道概率 DP 题卡了整整一下午后来把 exgcd 模板在手推纸上跑了好几遍才真正理解为什么 exgcd 返回的 x 取模之后就是逆元。所以我也建议你别光背板子拿笔把“3 在模 7 下的逆元”那一套正向、回溯的过程写一遍比看十篇博客都管用。下一篇我准备接着讲同余方程、中国剩余定理或者从逆元延伸出去的原根和离散对数如果你有更感兴趣的方向也可以留言告诉我。
写代码或者刷算法题的时候如果连续碰到“模一个素数”和“算一个分数”你大概率会被同一个东西卡住——逆元也叫数论倒数。比如要算 5 ÷ 3 mod 7你对着整数除法想半天也得不到一个“正常”答案因为在模 7 的世界里除法根本没有被定义。逆元解决的就是这个问题把除法转换成乘法找一个数 x让 3 乘以 x 之后在模 7 意义下等于 1。找到这个 x5 ÷ 3 就能变成 5 乘 x。就这么一个概念在数论、算法竞赛、密码学的 RSA 里反复出现。这篇文章作为系列 P1我打算从零开始把逆元是什么、怎么求、代码怎么写、新手容易踩哪些坑一次性讲透。适合刚接触数论的竞赛选手、对密码学感兴趣的程序员以及准备复试被数论问到的同学。今天讲的都是最基础也最核心的东西理解透了后面看原根、离散对数、二次剩余都会轻松很多。1. 数论倒数到底在算什么1.1 除法在模世界被卡住了先弄明白一件事模运算里加法、减法、乘法都很自然。7 小时转一圈的钟表上3 点加 5 小时是 1 点这本质上就是 (3 5) mod 7 1。乘法呢可以理解成多次加法比如 3 × 3 9在模 7 下等于 2也没毛病。可一旦碰到除法问题就来了5 ÷ 3 在模 7 下等于多少你要是直接做 5 ÷ 3得到的是 1.666...这是个小数而模 7 的世界里只有 0 到 6 这 7 个整数。就算你把 5 ÷ 3 想成“哪个整数乘以 3 之后等于 5”2 × 3 61 × 3 3试一圈也找不到一个整数能让它模 7 等于 5。换一种思路在实数里除法其实就是乘以这个数的倒数3 的倒数是 1/3因为 3 × (1/3) 1。那么在模 7 的世界里能不能也找一个“倒数”呢也就是说找一个小整数 x使 3 × x ≡ 1 (mod 7)。你挨个试3 × 1 33 × 2 63 × 3 9 ≡ 23 × 4 12 ≡ 53 × 5 15 ≡ 1。找到了x 5。这个 5就是 3 在模 7 意义下的“倒数”也叫乘法逆元。有了它5 ÷ 3 就能写成 5 × 5 25模 7 等于 4。你验证一下4 × 3 12 ≡ 5完全正确。所以逆元的本质就是用乘法去模拟除法让原本没法直接算的“模除法”变得可算。1.2 定义与存在条件不是所有数都有“钥匙”正式一点如果 ax ≡ 1 (mod m)就把 x 称为 a 在模 m 意义下的乘法逆元记作 a⁻¹。注意这个记号不是实数里的倒数但在模意义下它的行为和倒数一模一样a 乘以 a⁻¹ 的结果在模 m 下等于单位元 1。既然跟倒数这么像那第一个要搞清楚的问题就是是不是随便一个数都有逆元答案是不一定。逆元存在的充要条件是 gcd(a, m) 1也就是 a 和模数 m 互质。为什么把 ax ≡ 1 (mod m) 展开等价于存在整数 k使得 ax - km 1。如果 gcd(a, m) d 1那么 d 一定整除 ax也一定整除 km所以 d 必须整除 1这显然不可能。反过来如果 gcd(a, m) 1根据后面要讲的扩展欧几里得定理一定存在整数 x、k 满足 ax - km 1也就是逆元一定存在。所以“有没有逆元”这个问题本质上是“互不互质”的问题。这里有个很重要的推论当模数 m 是素数时1 到 m-1 之间所有整数都和 m 互质也就是说除了 0 和 m 的倍数之外每个数都有逆元。这就是为什么后面大量数论题目默认模数是 1000000007 这种大素数题目敢让你随便做除法就是因为每个非零数的逆元都存在。而一旦模数是合数比如模 4 之下2 就没有逆元你试遍 0、1、2、32 乘以任何数模 4 都只能是 0 或 2永远得不到 1。2. 求逆元的三种主流方法2.1 扩展欧几里得最通用的解法求逆元的第一个方法也是适用范围最广的方法叫扩展欧几里得算法简称 exgcd。大家都学过辗转相除法求 gcd它基于一个恒等式gcd(a, b) gcd(b, a mod b)一直递归到 b 0 时gcd 就是 a。扩展欧几里得在此基础上多算了一样东西它不光求出 gcd(a, b)还能同时找出一组整数 x、y使得 ax by gcd(a, b)。这个式子叫裴蜀定理意思是说两个数的最大公约数一定能写成这两个数的整数线性组合。把 b 换成 m如果 gcd(a, m) 1那 exgcd 返回的就是 ax my 1。把这个式子两边同时模 mmy 这一项直接消失剩下 ax ≡ 1 (mod m)所以 exgcd 返回的 x 就是逆元。举一个具体的例子求 3 在模 7 下的逆元。手动跑一遍7 2 × 3 1 1 7 - 2 × 3把第二个式子写成 3 × (-2) 7 × 1 1所以 x -2。但模 7 意义下-2 ≡ 5所以逆元是 5和前面试出来的结果一致。这里要注意exgcd 算出来的 x 可能是负数这时候一定要“修正”到 [0, m-1] 区间。方法就是 x (x % m m) % m先取模再加模再取模保证结果非负。exgcd 的复杂度是 O(log min(a, m))非常快。它的最大优势是模数不要求是素数只要互质就行所以它是处理合数模场景的底牌。2.2 费马小定理模素数的快速通道如果你确定模数 p 是素数那还有一条更快的路费马小定理。定理说对于素数 p且 gcd(a, p) 1有 a^(p-1) ≡ 1 (mod p)。这个式子可以变形a × a^(p-2) ≡ 1 (mod p)所以 a 的逆元就是 a^(p-2) mod p。只要用快速幂把 a^(p-2) 算出来逆元就拿到了。为什么费马小定理成立我给出一个直观的证明思路。考虑 a、2a、3a、...、(p-1)a 这 p-1 个数模 p 的结果。因为 gcd(a, p) 1每个数都不是 p 的倍数而且任意两个的差也不能被 p 整除所以它们模 p 后恰好是 1 到 p-1 的一个排列。把它们全部乘起来就有 a^(p-1) × (p-1)! ≡ (p-1)! (mod p)两边消去 (p-1)!就得到 a^(p-1) ≡ 1 (mod p)。这个方法在竞赛里用得最多原因很现实题目经常给你一个大素数模数比如 1e97、998244353这时候求逆元就是一行快速幂的事。需要注意的是费马小定理的前提是“p 是素数”只要模数是合数a^(m-2) 很可能不是逆元这一点后面专门讲坑。2.3 欧拉定理把素数的限制放宽费马小定理虽然好用但素数这个前提太苛刻了。如果模数是合数有没有一个更一般的定理有就是欧拉定理。欧拉定理说如果 gcd(a, m) 1那么 a^φ(m) ≡ 1 (mod m)其中 φ(m) 是欧拉函数表示 1 到 m 之间与 m 互质的整数个数。根据欧拉定理a 的逆元就是 a^(φ(m)-1) mod m。当 m 是素数 p 时φ(p) p-1欧拉定理就退化成费马小定理所以费马小定理其实是欧拉定理的特例。用欧拉定理求逆元的关键是算出 φ(m)。如果 m 不大可以暴力枚举统计互质数如果 m 很大一般要先分解质因数再运用公式 φ(m) m × ∏(1 - 1/p_i) 计算。每多一个质因子就乘上一个 (p-1)/p。这个公式在初等数论里很常用但本文 P1 阶段先不展开知道有这么一条通用路线即可。三种方法做个简单选型模数是素数优先费马小定理模数是合数但互质用扩展欧几里得最省事或者用欧拉定理而且 exgcd 还能用来判断逆元是否存在这个别名“万能底牌”不是白叫的。3. 直接能用的代码模板3.1 扩展欧几里得模板先上 C 的 exgcd 模板。代码很短但递归边界、引用传参这两点要记牢。#include bits/stdc.h using namespace std; 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 g exgcd(b, a % b, y, x); y - (a / b) * x; return g; } // 求 a 在模 m 下的逆元若不存在返回 -1 long long inv(long long a, long long m) { long long x, y; long long g exgcd(a, m, x, y); if (g ! 1) return -1; return (x % m m) % m; }递归到 b 0 的时候gcd 是 a此时显然 a × 1 0 × 0 a所以 x 1y 0。回溯的过程稍微有点绕关键是利用下一层的 x、y 来更新当前层的值。模板里直接递归时交换 x、y 的位置再修正 y这是最常见的写法我建议直接背熟。C 里要注意a、m 都可能达到 1e9 量级中途乘法可能溢出 int所以要用 long long。最后的(x % m m) % m这一步是必须的它能保证返回的是非负且小于 m 的逆元。Python 版更符合直觉直接同步返回 gcd 和一组解def exgcd(a, b): if b 0: return a, 1, 0 g, x1, y1 exgcd(b, a % b) return g, y1, x1 - (a // b) * y1 def inv(a, m): g, x, _ exgcd(a, m) if g ! 1: return -1 return (x % m m) % m用法验证inv(3, 7)返回 5inv(2, 4)返回 -1。这一份模板可以直接拿到平时的模运算场景里用。3.2 费马小定理 快速幂模板当模数 p 是大素数时逆元 a^(p-2) mod p核心就是快速幂。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; } // 调用方式p 必须是素数 long long inv_prime_mod(long long a, long long p) { return qpow(a, p - 2, p); }Python 更简单内置pow第三个参数就是模数内部已经是快速幂实现def inv_prime_mod(a, p): return pow(a, p - 2, p)有个细节提醒一下C 里的pow是浮点函数千万别和快速幂混淆我见过不少新手拿pow(a, p-2)去取模结果得到一个完全没有意义的大浮点数然后对着答案怀疑人生。写求逆元的代码老老实实用整型快速幂或者 Python 内置的三参 pow。3.3 从 1 连算到 n 的线性递推求逆元有时候题目要一次性算很多个数的逆元比如预处理 1!、2!、...、n! 的逆元。如果对每个数都跑一次 exgcd 或快速幂复杂度是 O(n log mod)数据一大就容易超时。这时候有个 O(n) 的线性递推公式前提同样是模数 p 为素数。公式是inv[i] -(p // i) * inv[p % i] % p写成防负数的代码就是vectorlong long inv_all(int n, long long p) { vectorlong long inv(n 1); inv[1] 1; for (int i 2; i n; i) { inv[i] (p - p / i) * inv[p % i] % p; } return inv; }这个公式怎么来的设 p (p // i) * i (p % i)两边在模 p 下看就有 p % i ≡ -(p // i) * i (mod p)。两边同时乘以 inv[p % i] × inv[i]得到 inv[i] ≡ -(p // i) * inv[p % i] (mod p)。把负号处理掉就是上面的写法。用 p 7 验证一下inv[1] 1inv[2] (7 - 3) × inv[1] % 7 4inv[3] (7 - 2) × inv[1] % 7 5inv[4] (7 - 1) × inv[3] % 7 6 × 5 % 7 2。你检查2 × 4 8 ≡ 13 × 5 15 ≡ 14 × 2 8 ≡ 1全部正确。有了这个数组后面算组合数取模就非常舒服。4. 实战里逆元的价值4.1 模意义下的分数与除法很多人第一次真正需要逆元是在做概率 DP、期望、递推这类题的时候。比如递推公式是 f[i] f[i-1] / k something所有结果都要对一个素数模取模。这时候你没法真的做小数除法因为取模只对整数有意义。正确做法是把“除以 k”换成“乘以 k 的逆元”。换句话说模意义下分数 a/b 定义为 a × b⁻¹ mod m。只要 b 和模数互质这个分数就有明确的整数取值。举个例子在模 7 下计算 5 / 2。inv(2, 7) 4所以 5 / 2 mod 7 5 × 4 20 ≡ 6。你验证6 × 2 12 ≡ 5完全正确。这个 6 在模 7 的世界里就扮演着“二分之五”的角色。这种操作在普通算术里看起来很奇怪但在模世界里是自洽的。4.2 组合数取模的经典套路再往实战走一步组合数取模大概是逆元出场率最高的地方。C(n, k) n! / (k! × (n-k)!)这里面有除法所以模素数 p 下不能直接算。但是只要预处理阶乘和阶乘的逆元组合数计算就变成了几次乘法。具体套路分三步预处理 fac[i]从 0 循环到 nfac[0] 1fac[i] fac[i-1] × i % p。用费马小定理算 fac[n] 的逆元然后反向递推得到所有阶乘逆元invfac[n] qpow(fac[n], p-2, p)invfac[i-1] invfac[i] × i % p。组合数 C(n, k) fac[n] × invfac[k] × invfac[n-k] % p。这个套路几乎是组合计数题的标配你能在无数题解里看到它。为什么需要反向递推而不是单独算每个阶乘逆元因为单个算是 O(n log p)反向递推只用一次快速幂总体 O(n)这在 n 到 1e6、1e7 的场景下区别很大。如果题目要求多个查询这个预处理的优势更明显。当 n、k 超过模数 p 时上面这个直接算的方法就不对了要用 Lucas 定理那是后面章节的内容但在 P1 阶段先把基础套路练熟。4.3 密码学里的一个小轮子逆元不是竞赛专属技巧它是密码学的地基。最典型的例子就是 RSA 算法里计算私钥 d 的过程。在 RSA 里选取两个大素数 p、qn p × qφ(n) (p-1)(q-1)。然后选一个加密指数 e使得 gcd(e, φ(n)) 1。解密指数 d 必须满足 ed ≡ 1 (mod φ(n))。这个 d 就是 e 在模 φ(n) 下的逆元求解方法正是扩展欧几里得算法。可以说没有模逆元RSA 的密钥生成逻辑就崩了。另外在一些哈希函数、伪随机数生成器、有限域运算的设计里也会用到模逆元来构造可逆映射。因为逆元保证“乘以一个数再乘以它的逆元”最后能回到原来的数这种可逆性在设计双向一致性的计算中非常宝贵。对初学者来说知道“逆元是密码学的基础零件之一”就够了真正深入可以在密码学课程里继续展开。5. 新手翻车现场常见问题与排查5.1 逆元不存在时的判断和替代方案最常遇到的翻车场景是模数是合数某个数根本没有逆元。典型例子求 2 在模 4 下的逆元你会发现 2 × 0 02 × 1 22 × 2 02 × 3 2永远得不到 1所以无解。用 exgcd 求逆元时返回的 gcd 不是 1 就说明无解这一点写完模板之后一定别丢。那无解怎么办看题目是否允许换一种方式比如把整条递推式稍微化简或者换一个大素数模数。如果题目设计没问题逆元一般都会被保证存在但作为写代码的人防御性检查很有必要不要一上来就除。5.2 负数取模的语言差异exgcd 返回的 x 经常是负数比如求 3 模 7 的逆元原始 exgcd 给出 x -2。如果不修正在 C 里直接 return -2你拿着去算 5 × (-2) mod 7结果可能变成 -3虽然 (5 × (-2)) mod 7 在数学上等价于 4但取模运算在 C 里对负数的结果也是负数很容易出锅。Python 倒是不一样负数取模会返回非负结果-2 % 7 等于 5所以习惯 Python 的选手可能不会意识到这个问题一旦切到 C 就容易栽。统一的处理方法是 (x % m m) % m把可能为负的 x 调到 [0, m-1] 区间。这个修正对任何语言都适用建议封装进 inv 函数里。5.3 乘法溢出与超大模数的处理当模数 p 是 1e97int 最多到大概 21 亿p × p 已经超过 int 上限所以代码里 a × a % mod 这行a 和 a 相乘可能直接溢出变成负数。C 里解决办法是全部用 long long 存中间变量。当 p 本身达到 1e18 级别long long 相乘也会溢出这时候就要用更高级的手段比如基于二进制分解的快速乘或者直接用__int128临时存中间结果。竞赛里一般用不上但一旦遇到知道有这么回事就能少走弯路。5.4 费马小定理的误用场景把 a^(m-2) mod m 当逆元用前提是 m 为素数。如果 m 是合数费马小定理不成立结果基本是错的。我见过有人用 m 15a 2 去测直接得出一个“看起来像模运算的数”结果完全对不上然后开始怀疑自己代码写错了。实际处理时先确认题目里的模数是不是素数。如果是类似 1e97、998244353 这类基本可以确定是素数放心用费马小定理。如果不是就用 exgcd 判断并求逆元千万不要把一个合数当成素数开 floyd 式骚操作。下面把几个常见问题整理成表常见问题原因解决办法逆元返回负数exgcd 解出来的 x 可能为负统一做 (x % m m) % mgcd 不为 1a 和 m 不互质逆元不存在换互质的模数或换计算方式费马小定理算错模数不是素数误用 a^(p-2)用 exgcd 或欧拉定理乘法溢出a × a 超过 int/long long 范围中间量用 long long必要时 __int128批量逆元太慢每个数单独快速幂用 inv[i] 递推 O(n) 求全部最后再分享一个我自己的小经验。我当年学逆元是在做一道概率 DP 题卡了整整一下午后来把 exgcd 模板在手推纸上跑了好几遍才真正理解为什么 exgcd 返回的 x 取模之后就是逆元。所以我也建议你别光背板子拿笔把“3 在模 7 下的逆元”那一套正向、回溯的过程写一遍比看十篇博客都管用。下一篇我准备接着讲同余方程、中国剩余定理或者从逆元延伸出去的原根和离散对数如果你有更感兴趣的方向也可以留言告诉我。
