在实际的算法题和工程开发里几乎每个人都会遇到这种尴尬要在模数下算(a / b) % MOD直接除会丢精度转浮点更是灾难。正确思路是“除法变乘法”也就是先求b的乘法逆元再算a * inv(b) % MOD。而乘法逆元最通用、最稳定的求法之一就是 exgcd扩展欧几里得。我这篇不打算只丢一个模板就完事我会把 exgcd 为什么能求出逆元、递归里系数到底怎么变、代码怎么写不容易错、以及我在模拟项目 X 里踩过的坑一次讲清楚。适合正在啃数论算法、准备比赛或者被模运算恶心过的开发者。1. 模运算下的除法为什么离不开乘法逆元1.1 把除法变成乘法的那个数先回顾一下定义。如果存在整数x满足b * x ≡ 1 (mod m)那x就是b在模m下的乘法逆元记作b^{-1} mod m。注意这里的“逆元”不是倒数是一个“在模意义下和倒数同等作用”的整数。比如在模 7 下3 的逆元是 5因为3 * 5 15 ≡ 1 (mod 7)。有了这个逆元原来的除法就能写成a / b ≡ a * x (mod m)逻辑也很直接假设b * x ≡ 1 (mod m)两边同时乘a就得到a * b * x ≡ a (mod m)再做一个“除以 b”的视觉操作本质上用的是同余式两边乘同一个数的性质。所以求逆元的本质不是把数倒过来而是找一个能在模意义下“抵消”掉 b 的量。这个转化特别重要因为很多取模问题里直接算除法就会碰到“模数不能被整除”的尴尬。比如(6 / 2) % 5当然可以直接算成 3但如果分子很大、分母很大或者结果本身不整除浮点数一进来就废了。有了逆元所有除法都变成整数乘法之后再用快速幂、组合数公式就非常顺畅。1.2 逆元不是什么时候都存在互质是硬门槛很多人第一次学逆元时有个误区觉得“任何数都能求逆元”。真不是。模 4 下2 有逆元吗2 乘以 1、2、3分别得到 2、0、2永远得不到 1所以 2 在模 4 下没有逆元。判断条件就一句话b和模数m必须互质也就是gcd(b, m) 1。为什么如果存在x使得b*x ≡ 1 (mod m)那意味着存在整数k让b*x 1 m*k整理成b*x - m*k 1。左边是两个整数的线性组合而gcd(b, m)一定能整除左边。如果公因数不是 1左边就不可能等于 1矛盾。反过来如果gcd(b, m) 1数学上的贝祖定理保证一定存在一组整数x, k使等式成立。而怎样把这组系数高效地找出来正是 exgcd 的工作。明白这一点很有用。以后遇到“为什么这里没逆元”第一反应是算gcd而不是怀疑代码写错了。2. exgcd 求乘法逆元的原理拆解2.1 贝祖等式与扩展欧几里得的关系普通欧几里得算法大家都会gcd(a, b) gcd(b, a % b)一直递归到余数为 0。但普通算法只返回最大公约数exgcd 多返回两组系数让它满足a * x b * y gcd(a, b)这个等式就是贝祖等式。为什么它和逆元有关把这里的b换成模数m再令g gcd(a, m)。如果g 1那么a * x m * y 1两边同时对m取模左边第二项m*y被模掉得到a * x ≡ 1 (mod m)这不就是逆元的定义吗所以 exgcd 求出的x根本就是逆元。不需要额外发明新算法也不必先判断质数只要gcd(a, m) 1exgcd 就能给出答案。这也是它在工程里比费马小定理更通用的根本原因。2.2 递归回溯时系数到底怎么变回来只看结论容易背错我把递归推导写一遍。假设一次调用是exgcd(a, b)递归进去得到exgcd(b, a % b)的结果记为(g, x1, y1)满足b * x1 (a % b) * y1 g关键的置换是a % b a - (a // b) * b代回去b * x1 [a - (a // b) * b] * y1 a * y1 b * (x1 - (a // b) * y1)现在和a*x b*y g对照自然得到x y1 y x1 - (a // b) * y1递归到底的条件是b 0。此时gcd(a, 0) a所以取x 1, y 0因为a*1 0*0 a。这里最常见的误区是把边界写成x0, y1一错就全错。为了更直观我拿exgcd(3, 7)走一遍。递归顺序是往下压返回时往上带系数。递归层调用返回的 x,y该层等式1exgcd(1, 0)(1, 0)110012exgcd(3, 1)(0, 1)301113exgcd(7, 3)(1, -2)713(-2)14exgcd(3, 7)(-2, 1)3*(-2)7*11最后一层返回x -2而-2 mod 7 5正好就是 3 在模 7 下的逆元。这也说明一个问题exgcd 给的逆元经常是负数要记得取模修正成最小正整数。后面代码里统一用(x % m m) % m。3. 用 exgcd 求逆元的实现与避坑3.1 一个可以“抄作业”的递归模板先给 Python 版本读起来和上面的推导一一对应def exgcd(a, b): if b 0: return a, 1, 0 g, x1, y1 exgcd(b, a % b) x y1 y x1 - (a // b) * y1 return g, x, y def mod_inverse(a, m): a % m g, x, _ exgcd(a, m) if g ! 1: return None 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 x1, y1; long long g exgcd(b, a % b, x1, y1); x y1; y x1 - (a / b) * y1; return g; } long long mod_inverse(long long a, long long m) { a (a % m m) % m; long long x, y; long long g exgcd(a, m, x, y); if (g ! 1) return -1; return (x % m m) % m; }先取a % m是为了把负数、超过模数的输入统一到[0, m-1]。这个习惯非常重要否则后面所有推导都和正数假设冲突。3.2 负数、溢出和模数边界平时最容易出问题的有两个地方。第一负数的取模行为。C 里-3 % 5得到-3而 Python 里得到2。如果直接把负数传给 exgcd虽然数学上系数仍然可能正确但遇到a // b这种向下取整和 C 的截断取整混在一起很容易出意外。稳妥做法就是先a (a % m m) % m强制转成非负。第二C 的乘法溢出。虽然 exgcd 本身只有加减乘除但回溯公式里有(a / b) * y1。如果a和y1都是接近1e18的量级乘积直接爆long long。解决方案是计算中间量时用__int128算完再转回long long如果模数本身只有1e9那long long就足够安全。Python 没有这个问题但速度上要权衡。模数边界也提一下m 0时“模 m”无意义m 1时所有整数都同余于 0逆元概念退化直接返回错误即可。实际场景里模数都是正整数但做通用函数时最好主动检查。3.3 验证逆元的成本很低一定要做写完函数第一件事不是丢进业务而是做一轮穷举验证。对m较小的情况从1到m-1逐个跑for a in range(1, m): inv mod_inverse(a, m) if inv is None or (a * inv) % m ! 1: print(error, a, inv) break这一步能在五分钟内帮你把边界写错、取模方向写反、递归系数弄反这些坑全部揪出来。C 里验证乘法则要用__int128兜底if ((__int128)a * inv % m ! 1) { /* error */ }别嫌麻烦。我之前就是在模拟项目 X 里没做这步直接把某个模数当质数传给快速幂结果平台上报了一串奇怪的判题错误后来才发现那个模数是合数gcd根本不是 1。4. 常见问题与排查实录4.1 逆元不存在的场景一眼识别如果gcd(a, m) ! 1mod_inverse会返回None或-1。但很多人写的模板里没有这个判断直接把 exgcd 返回的x当答案输出了。比如模 6 下求 4 的逆元gcd(4, 6)2exgcd 其实也能返回一组满足4x6y2的系数但4x ≡ 1 (mod 6)根本无解。所以函数里必须显式检查g ! 1。这里有个容易迷惑的点gcd(a, m)等于 1和“a 在模 m 下有逆元”完全等价。不需要额外去试乘直接算 gcd 就行。如果发现没有逆元解决办法通常是先除以公因数把同余方程约简而不是硬求。4.2 exgcd 和费马小定理怎么选很多人会纠结到底用 exgcd 还是费马小定理。我直接给个对比对比项exgcd 求逆元费马小定理求逆元适用条件gcd(a, m)1模数任意正整数m为素数且 a 不是 m 的倍数背后原理贝祖等式费马小定理a^(m-1) ≡ 1实现成本递归约十几行快速幂约十行时间复杂度O(log min(a, m))O(log m)典型场景模数是合数、模数动态变化模数是固定质数比如 1e97理论上两者复杂度都是对数级差别很小。如果竞赛题目里模数固定是质数用费马小定理最省心如果模数可能不是质数、或者每次询问模数不一样那就必须用 exgcd。还有一个折中方式Python 3.8 之后内置的pow(a, -1, m)底层就是扩展欧几里得算法但做工程和算法题时自己写过一遍才能放心。4.3 实战排查清单我把实际调试中遇到的状况整理成一份速查表以后照着查就行症状可能原因处理方式返回负数没有做最小正整数修正统一(x % m m) % m结果乘回去不等于 1递归系数写反或边界写错对照xy1, yx1-(a//b)*y1大模数下程序溢出中间乘法超过 long long用__int128或缩小输入gcd1 却显示无逆元函数里漏了取模修正先a % m再进 exgcd模数变化时答案随机误用了费马小定理改成 exgcd 并检查互质排查时建议先小范围穷举再对数器验证最后才上大数据。大多数逆元 bug 在m小于 30 时就能暴露。5. 把逆元放进实战两个场景 一点习惯5.1 解同余方程同余方程是逆元最直接的用途之一形如a * x ≡ b (mod m)如果gcd(a, m) 1方程有唯一解直接在两边乘a^{-1}就行。但如果gcd(a, m) g 1就要先判断g是否能整除b。不能整除说明无解能整除先把两边和模数都除以ga a / g b b / g m m / g此时gcd(a, m) 1再用 exgcd 求a在模m下的逆元。但要注意约简之后得到的解是模m下的唯一解回到原模m时会有g个不同的剩余类解。举个例子解6x ≡ 12 (mod 24)。gcd(6, 24)6而 6 能整除 12于是约简为x ≡ 2 (mod 4)。原模 24 下所有满足条件的解就是2,6,10,14,18,22一共 6 个。如果不先约简就硬用 exgcd会漏掉很多解甚至误判无解。5.2 组合数取模时的逆元预处理组合数公式里有个除法C(n, k) n! / (k! * (n-k)!)如果要在模m下计算分母这些阶乘都得转化成逆元。一个常见做法是预处理阶乘和阶乘逆元数组fac[0] 1 for i in range(1, n1): fac[i] fac[i-1] * i % m ifac[n] mod_inverse(fac[n], m) for i in range(n, 0, -1): ifac[i-1] ifac[i] * i % m这样求组合数就是fac[n] * ifac[k] * ifac[n-k] % m全程没有除法只有乘法取模速度和稳定性都很高。但这里的前提是每个阶乘和模数互质。如果模数是固定质数用费马小定理预处理更省事如果模数是合数就必须小心必要时还得请出扩展 Lucas。不过不管用哪种理解 exgcd 求逆元都是基本功。5.3 我每次写完逆元函数必做的一件事最后分享一个个人习惯写完mod_inverse一定不会立刻写业务逻辑。我会先跑一段穷举验证再把验证断言留在代码里当成调试开关。这不是强迫症而是逆元这种基础函数一旦出错上层组合数、同余方程全都会跟着错而且错得毫无规律特别难查。用assert (a * inv) % m 1这种断言能把问题锁死在第一层。另外如果代码里允许直接用 Python 3.8 的pow(a, -1, m)我也建议先用它跑一遍对拍确认自己的 exgcd 结果一致。这种“自己实现 标准库对拍”的组合是我在实际开发中用过最省心的验证方式。别小看这个习惯它帮我在模拟项目 X 里省下过一整个晚上的排查时间。 
长河君 · 2026/10/10 4:28:39 · 阅读 1.2k 扩展欧几里得算法求乘法逆元：原理、实现与工程避坑指南
在实际的算法题和工程开发里几乎每个人都会遇到这种尴尬要在模数下算(a / b) % MOD直接除会丢精度转浮点更是灾难。正确思路是“除法变乘法”也就是先求b的乘法逆元再算a * inv(b) % MOD。而乘法逆元最通用、最稳定的求法之一就是 exgcd扩展欧几里得。我这篇不打算只丢一个模板就完事我会把 exgcd 为什么能求出逆元、递归里系数到底怎么变、代码怎么写不容易错、以及我在模拟项目 X 里踩过的坑一次讲清楚。适合正在啃数论算法、准备比赛或者被模运算恶心过的开发者。1. 模运算下的除法为什么离不开乘法逆元1.1 把除法变成乘法的那个数先回顾一下定义。如果存在整数x满足b * x ≡ 1 (mod m)那x就是b在模m下的乘法逆元记作b^{-1} mod m。注意这里的“逆元”不是倒数是一个“在模意义下和倒数同等作用”的整数。比如在模 7 下3 的逆元是 5因为3 * 5 15 ≡ 1 (mod 7)。有了这个逆元原来的除法就能写成a / b ≡ a * x (mod m)逻辑也很直接假设b * x ≡ 1 (mod m)两边同时乘a就得到a * b * x ≡ a (mod m)再做一个“除以 b”的视觉操作本质上用的是同余式两边乘同一个数的性质。所以求逆元的本质不是把数倒过来而是找一个能在模意义下“抵消”掉 b 的量。这个转化特别重要因为很多取模问题里直接算除法就会碰到“模数不能被整除”的尴尬。比如(6 / 2) % 5当然可以直接算成 3但如果分子很大、分母很大或者结果本身不整除浮点数一进来就废了。有了逆元所有除法都变成整数乘法之后再用快速幂、组合数公式就非常顺畅。1.2 逆元不是什么时候都存在互质是硬门槛很多人第一次学逆元时有个误区觉得“任何数都能求逆元”。真不是。模 4 下2 有逆元吗2 乘以 1、2、3分别得到 2、0、2永远得不到 1所以 2 在模 4 下没有逆元。判断条件就一句话b和模数m必须互质也就是gcd(b, m) 1。为什么如果存在x使得b*x ≡ 1 (mod m)那意味着存在整数k让b*x 1 m*k整理成b*x - m*k 1。左边是两个整数的线性组合而gcd(b, m)一定能整除左边。如果公因数不是 1左边就不可能等于 1矛盾。反过来如果gcd(b, m) 1数学上的贝祖定理保证一定存在一组整数x, k使等式成立。而怎样把这组系数高效地找出来正是 exgcd 的工作。明白这一点很有用。以后遇到“为什么这里没逆元”第一反应是算gcd而不是怀疑代码写错了。2. exgcd 求乘法逆元的原理拆解2.1 贝祖等式与扩展欧几里得的关系普通欧几里得算法大家都会gcd(a, b) gcd(b, a % b)一直递归到余数为 0。但普通算法只返回最大公约数exgcd 多返回两组系数让它满足a * x b * y gcd(a, b)这个等式就是贝祖等式。为什么它和逆元有关把这里的b换成模数m再令g gcd(a, m)。如果g 1那么a * x m * y 1两边同时对m取模左边第二项m*y被模掉得到a * x ≡ 1 (mod m)这不就是逆元的定义吗所以 exgcd 求出的x根本就是逆元。不需要额外发明新算法也不必先判断质数只要gcd(a, m) 1exgcd 就能给出答案。这也是它在工程里比费马小定理更通用的根本原因。2.2 递归回溯时系数到底怎么变回来只看结论容易背错我把递归推导写一遍。假设一次调用是exgcd(a, b)递归进去得到exgcd(b, a % b)的结果记为(g, x1, y1)满足b * x1 (a % b) * y1 g关键的置换是a % b a - (a // b) * b代回去b * x1 [a - (a // b) * b] * y1 a * y1 b * (x1 - (a // b) * y1)现在和a*x b*y g对照自然得到x y1 y x1 - (a // b) * y1递归到底的条件是b 0。此时gcd(a, 0) a所以取x 1, y 0因为a*1 0*0 a。这里最常见的误区是把边界写成x0, y1一错就全错。为了更直观我拿exgcd(3, 7)走一遍。递归顺序是往下压返回时往上带系数。递归层调用返回的 x,y该层等式1exgcd(1, 0)(1, 0)110012exgcd(3, 1)(0, 1)301113exgcd(7, 3)(1, -2)713(-2)14exgcd(3, 7)(-2, 1)3*(-2)7*11最后一层返回x -2而-2 mod 7 5正好就是 3 在模 7 下的逆元。这也说明一个问题exgcd 给的逆元经常是负数要记得取模修正成最小正整数。后面代码里统一用(x % m m) % m。3. 用 exgcd 求逆元的实现与避坑3.1 一个可以“抄作业”的递归模板先给 Python 版本读起来和上面的推导一一对应def exgcd(a, b): if b 0: return a, 1, 0 g, x1, y1 exgcd(b, a % b) x y1 y x1 - (a // b) * y1 return g, x, y def mod_inverse(a, m): a % m g, x, _ exgcd(a, m) if g ! 1: return None 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 x1, y1; long long g exgcd(b, a % b, x1, y1); x y1; y x1 - (a / b) * y1; return g; } long long mod_inverse(long long a, long long m) { a (a % m m) % m; long long x, y; long long g exgcd(a, m, x, y); if (g ! 1) return -1; return (x % m m) % m; }先取a % m是为了把负数、超过模数的输入统一到[0, m-1]。这个习惯非常重要否则后面所有推导都和正数假设冲突。3.2 负数、溢出和模数边界平时最容易出问题的有两个地方。第一负数的取模行为。C 里-3 % 5得到-3而 Python 里得到2。如果直接把负数传给 exgcd虽然数学上系数仍然可能正确但遇到a // b这种向下取整和 C 的截断取整混在一起很容易出意外。稳妥做法就是先a (a % m m) % m强制转成非负。第二C 的乘法溢出。虽然 exgcd 本身只有加减乘除但回溯公式里有(a / b) * y1。如果a和y1都是接近1e18的量级乘积直接爆long long。解决方案是计算中间量时用__int128算完再转回long long如果模数本身只有1e9那long long就足够安全。Python 没有这个问题但速度上要权衡。模数边界也提一下m 0时“模 m”无意义m 1时所有整数都同余于 0逆元概念退化直接返回错误即可。实际场景里模数都是正整数但做通用函数时最好主动检查。3.3 验证逆元的成本很低一定要做写完函数第一件事不是丢进业务而是做一轮穷举验证。对m较小的情况从1到m-1逐个跑for a in range(1, m): inv mod_inverse(a, m) if inv is None or (a * inv) % m ! 1: print(error, a, inv) break这一步能在五分钟内帮你把边界写错、取模方向写反、递归系数弄反这些坑全部揪出来。C 里验证乘法则要用__int128兜底if ((__int128)a * inv % m ! 1) { /* error */ }别嫌麻烦。我之前就是在模拟项目 X 里没做这步直接把某个模数当质数传给快速幂结果平台上报了一串奇怪的判题错误后来才发现那个模数是合数gcd根本不是 1。4. 常见问题与排查实录4.1 逆元不存在的场景一眼识别如果gcd(a, m) ! 1mod_inverse会返回None或-1。但很多人写的模板里没有这个判断直接把 exgcd 返回的x当答案输出了。比如模 6 下求 4 的逆元gcd(4, 6)2exgcd 其实也能返回一组满足4x6y2的系数但4x ≡ 1 (mod 6)根本无解。所以函数里必须显式检查g ! 1。这里有个容易迷惑的点gcd(a, m)等于 1和“a 在模 m 下有逆元”完全等价。不需要额外去试乘直接算 gcd 就行。如果发现没有逆元解决办法通常是先除以公因数把同余方程约简而不是硬求。4.2 exgcd 和费马小定理怎么选很多人会纠结到底用 exgcd 还是费马小定理。我直接给个对比对比项exgcd 求逆元费马小定理求逆元适用条件gcd(a, m)1模数任意正整数m为素数且 a 不是 m 的倍数背后原理贝祖等式费马小定理a^(m-1) ≡ 1实现成本递归约十几行快速幂约十行时间复杂度O(log min(a, m))O(log m)典型场景模数是合数、模数动态变化模数是固定质数比如 1e97理论上两者复杂度都是对数级差别很小。如果竞赛题目里模数固定是质数用费马小定理最省心如果模数可能不是质数、或者每次询问模数不一样那就必须用 exgcd。还有一个折中方式Python 3.8 之后内置的pow(a, -1, m)底层就是扩展欧几里得算法但做工程和算法题时自己写过一遍才能放心。4.3 实战排查清单我把实际调试中遇到的状况整理成一份速查表以后照着查就行症状可能原因处理方式返回负数没有做最小正整数修正统一(x % m m) % m结果乘回去不等于 1递归系数写反或边界写错对照xy1, yx1-(a//b)*y1大模数下程序溢出中间乘法超过 long long用__int128或缩小输入gcd1 却显示无逆元函数里漏了取模修正先a % m再进 exgcd模数变化时答案随机误用了费马小定理改成 exgcd 并检查互质排查时建议先小范围穷举再对数器验证最后才上大数据。大多数逆元 bug 在m小于 30 时就能暴露。5. 把逆元放进实战两个场景 一点习惯5.1 解同余方程同余方程是逆元最直接的用途之一形如a * x ≡ b (mod m)如果gcd(a, m) 1方程有唯一解直接在两边乘a^{-1}就行。但如果gcd(a, m) g 1就要先判断g是否能整除b。不能整除说明无解能整除先把两边和模数都除以ga a / g b b / g m m / g此时gcd(a, m) 1再用 exgcd 求a在模m下的逆元。但要注意约简之后得到的解是模m下的唯一解回到原模m时会有g个不同的剩余类解。举个例子解6x ≡ 12 (mod 24)。gcd(6, 24)6而 6 能整除 12于是约简为x ≡ 2 (mod 4)。原模 24 下所有满足条件的解就是2,6,10,14,18,22一共 6 个。如果不先约简就硬用 exgcd会漏掉很多解甚至误判无解。5.2 组合数取模时的逆元预处理组合数公式里有个除法C(n, k) n! / (k! * (n-k)!)如果要在模m下计算分母这些阶乘都得转化成逆元。一个常见做法是预处理阶乘和阶乘逆元数组fac[0] 1 for i in range(1, n1): fac[i] fac[i-1] * i % m ifac[n] mod_inverse(fac[n], m) for i in range(n, 0, -1): ifac[i-1] ifac[i] * i % m这样求组合数就是fac[n] * ifac[k] * ifac[n-k] % m全程没有除法只有乘法取模速度和稳定性都很高。但这里的前提是每个阶乘和模数互质。如果模数是固定质数用费马小定理预处理更省事如果模数是合数就必须小心必要时还得请出扩展 Lucas。不过不管用哪种理解 exgcd 求逆元都是基本功。5.3 我每次写完逆元函数必做的一件事最后分享一个个人习惯写完mod_inverse一定不会立刻写业务逻辑。我会先跑一段穷举验证再把验证断言留在代码里当成调试开关。这不是强迫症而是逆元这种基础函数一旦出错上层组合数、同余方程全都会跟着错而且错得毫无规律特别难查。用assert (a * inv) % m 1这种断言能把问题锁死在第一层。另外如果代码里允许直接用 Python 3.8 的pow(a, -1, m)我也建议先用它跑一遍对拍确认自己的 exgcd 结果一致。这种“自己实现 标准库对拍”的组合是我在实际开发中用过最省心的验证方式。别小看这个习惯它帮我在模拟项目 X 里省下过一整个晚上的排查时间。