★ FEATURED ARTICLE 1. 先弄明白乘法逆元到底是什么一直用 Java 刷算法题或者写代码的朋友肯定都遇到过这么一个问题模运算里加减乘都好说唯独除法没法直接算。比如你在模 1_000_000_007 的意义下想算 a / b不可能直接拿 a 整除 b 然后取模因为中间结果早就不是普通的实数除法了。这时候就需要乘法逆元。乘法逆元简单讲就是在模 p 的世界里找一个数 x让 a * x % p 等于 1。这个 x 就是 a 在模 p 下的逆元一般记作 a^(-1)。有了它a / b 就能转换成 a * b^(-1) % p也就是把“除以 b”变成“乘以 b 的逆元”。这套操作在组合数计算、哈希处理、加密算法的底层实现里都是家常便饭。求逆元的方法有不少但我在 Java 里最常用的其实就两种一种是基于费马小定理用快速幂直接算另一种是扩展欧几里得算法把问题转化成解不定方程。这两种方法各有各的脾性适用场景也不完全一样。这篇文章就把两条路都走一遍代码、原理、坑点一次讲透适合刚开始学数论的算法选手也适合需要在生产代码里做模运算处理的 Java 开发者。我会尽量讲清楚“为什么”而不是只丢给你一段能跑的代码。2. 方法一费马小定理求逆元2.1 费马小定理说了什么费马小定理的内容很简单如果 p 是一个质数而 a 不是 p 的倍数那么 a^(p-1) ≡ 1 (mod p)。换句话说a 的 p-1 次方在模 p 下等于 1。我第一次看到这个定理的时候觉得它有点神奇因为它把“指数”和“模”联系在了一起但仔细推敲一下它本质上是在说在模质数 p 的世界里所有非零元素的循环周期是 p-1。怎么理解你可以想象一个只有 p 个刻度的钟表数字 0 到 p-1 围成一个环。a 不断乘上自己得到的序列一定会回到起点。对于质数 p 来说这个“绕一圈”的步数恰好是 p-1。这不是巧合而是因为模 p 剩余系里除 0 以外的 p-1 个数构成了一个乘法群群的大小就是 p-1任何元素的幂次周期必然整除群的大小。这个定理给求逆元带来了一个极漂亮的推论。既然 a^(p-1) ≡ 1那我把它拆一下a * a^(p-2) ≡ 1 (mod p)看到没a^(p-2) 刚好就是 a 的逆元。所以只要用快速幂算出 a^(p-2) mod p逆元就到手了。整个过程只需要一次 O(log p) 的幂运算思路非常干净。2.2 适用条件必须记清楚费马小定理这条路有一个硬性前提模数 p 必须是质数并且 a 不能是 p 的倍数。如果 p 不是质数这个定理直接失效因为剩余系里的乘法群结构会变周期不再是 p-1你拿 a^(p-2) 算出来的东西大概率不是逆元。竞赛里最常见的模数 1_000_000_007 恰好是质数所以费马小定理几乎成了默认做法。但我自己在实际项目里也遇到过模数是合数的情况比如模 10、模 12这时候就得老老实实换扩展欧几里得。提醒一句写代码前先确认 p 是不是质数别看到“费马小定理”四个字就往里套。很多初学者踩的坑不是代码写错而是定理用错了场景。2.3 Java 实现快速幂三步走用 Java 写快速幂其实非常顺手核心思想就是二分指数。我直接把完整代码贴出来然后逐行解释一下/** * 快速幂计算 (a^b) % mod * 时间复杂度 O(log b) */ static long qpow(long a, long b, long mod) { long res 1 % mod; a % mod; while (b 0) { if ((b 1) 1) { res res * a % mod; } a a * a % mod; b 1; } return res; } /** * 费马小定理求逆元 * 前置条件mod 是质数且 a 与 mod 互质 */ static long modInverseFermat(long a, long mod) { return qpow(a, mod - 2, mod); }快速幂的关键在于把 b 看成二进制数从低位到高位逐步处理。比如 b 13二进制是 1101那 a^13 就等于 a^8 * a^4 * a^1。循环里每一次都把 a 平方对应到二进制位的权重从 1 倍变成 2 倍、4 倍、8 倍如果当前位是 1就把累积结果乘上当前的 a。这样原本需要 13 次乘法现在只需要 4 次迭代指数越大优势越明显。有一个细节容易被忽略res 1 % mod而不是直接写res 1。当 mod 为 1 的时候这两种写法结果不同虽然实战中很少有人会传 mod1但写成1 % mod更严谨能避免一些极端情况下的 bug。2.4 为什么 res 初始值要取模乘法又该怎么处理很多人问过我快速幂里a a * a % mod不会溢出吗这个问题问得非常关键。Java 的 long 是 64 位有符号整数最大能表示约 9.22e18。如果 a 本身已经接近 mod 量级而 mod 又是 1e9 级别那么 a * a 最多到 1e18还在 long 的范围里不会溢出。但小心一点总没错如果模数超过 1e9比如接近 1e10那 a * a 就可能冲到 1e20直接爆掉 long。这时候要么用 BigInteger要么用快速乘法也叫龟速乘来模拟乘法取模避免溢出。我在自己写的模板里还会额外保证 a 在每次乘法前已经取过模这样乘法结果的上界可控。比如res res * a % mod这一行res 和 a 都已经小于 mod乘积小于 mod^2只要 mod^2 没超过 long 的最大值就是安全的。对于竞赛常用的 1e97 这个量级long 完全够用。另外快速幂的时间复杂度是 O(log p)空间复杂度是 O(1)不依赖递归没有栈溢出的风险。这是它比某些递归写法更稳的一个原因。实测下来在 Java 里求一次 1e9 级别模数的逆元耗时基本是微秒级完全可以接受。3. 方法二扩展欧几里得算法3.1 从辗转相除法到扩展欧几里得如果模数不是质数费马小定理这条路就走不通了这时候我一般会换扩展欧几里得算法。它不要求模数是质数只要求 a 和模数互质。这个条件比“模数是质数”宽松得多所以扩展欧几里得的适用面更广。先回顾一下欧几里得算法也就是辗转相除法gcd(a, b) gcd(b, a % b)一直递归到 b 0 时gcd(a, 0) a。这个算法大家很熟了不再多讲。扩展欧几里得多做了一件事在求出 gcd(a, b) 的同时找出一组整数解 x 和 y满足a * x b * y gcd(a, b)这个等式就是贝祖定理的核心形式。当 gcd(a, b) 1 时等式变成 a * x b * y 1。两边同时模 b得到 a * x ≡ 1 (mod b)也就是说 x 就是 a 在模 b 下的逆元。整个过程相当于把求逆元问题转化成了解方程问题数学上特别顺。3.2 递归推导从上一层的解推出当前层的解扩展欧几里得的递归代码很有意思核心就几行但很多人第一遍看会卡在 x 和 y 的迭代关系上。我还是把递归版完整写出来/** * 扩展欧几里得算法 * return long[] {x, y, gcd(a,b)}满足 a*x b*y gcd(a, b) */ static long[] exgcd(long a, long b) { if (b 0) { return new long[]{1, 0, a}; } long[] res exgcd(b, a % b); long x res[1]; long y res[0] - (a / b) * res[1]; return new long[]{x, y, res[2]}; } /** * 用扩展欧几里得求 a 在模 mod 下的逆元 * return 逆元如果不存在gcd ! 1返回 -1 */ static long modInverseExgcd(long a, long mod) { long[] res exgcd(a, mod); if (res[2] ! 1) { return -1; } return (res[0] % mod mod) % mod; }推导过程是这样的假设下一层递归已经算出了b * x1 (a % b) * y1 gcd那么我需要从这个等式反推出当层的 x 和 y。注意到a % b a - (a / b) * b把它代进去b * x1 (a - (a / b) * b) * y1 gcd整理一下把含 a 的项和含 b 的项分开a * y1 b * (x1 - (a / b) * y1) gcd所以当层的 x y1y x1 - (a / b) * y1。这就是代码里x res[1]和y res[0] - (a / b) * res[1]的来源。递归到最底层 b 0 的时候gcd a此时 x 1y 0因为 1 * a 0 * 0 a。然后一层一层往回带最终得到一组完整解。3.3 非递归版本避免递归栈开销递归版本虽然清晰但有一个实际问题如果递归深度很深Java 的调用栈可能撑不住。不过话说回来扩展欧几里得递归深度大约等于辗转相除法的迭代次数对于 1e9 量级的数来说深度也就几十层一般不会爆栈。我在生产代码里更偏爱非递归版本因为不用传数组返回也不容易踩栈的坑/** * 扩展欧几里得算法非递归实现 * 返回值是 long[] {x, y, gcd} */ static long[] exgcdIter(long a, long b) { long x0 1, y0 0; // 对应当前 a 的系数 long x1 0, y1 1; // 对应当前 b 的系数 while (b ! 0) { long q a / b; long tmp a; a b; b tmp % b; // 更新 (x, y) tmp x0; x0 x1; x1 tmp - q * x1; tmp y0; y0 y1; y1 tmp - q * y1; } return new long[]{x0, y0, a}; }这个版本维护两组系数一组跟着 a一组跟着 b每一步除法商 q 都会更新它们的线性组合。本质上就是在模拟递归过程但省去了函数调用和数组分配。实际跑下来在大数场景下它和递归版本的结果完全一致性能略微好一点。不过对于一般题目量级两者差别不大选你喜欢的风格即可。3.4 为什么这里不要求模数是质数这是扩展欧几里得最大的优势。它只要求 gcd(a, mod) 1并不关心 mod 是不是质数。原因也很直观模 mod 的剩余系里一个数 a 存在乘法逆元的充分必要条件就是 a 与 mod 互质。只要互质方程 a * x mod * y 1 一定存在整数解扩展欧几里得一定能把它找出来。举个例子模 10 之下3 的逆元是多少gcd(3, 10) 1所以存在逆元。用扩展欧几里得可以解出 3 * 7 10 * (-2) 1因此 3 的逆元是 7。如果用费马小定理就没法算因为 10 不是质数。这种场景在实际业务代码里不少见比如处理时间戳取模、哈希分片、校验码计算时模数经常不是质数扩展欧几里得就派上大用场了。4. 两套方案的横向对比与选型建议4.1 适用条件不一样费马小定理要求模数必须是质数这是它的适用前提。扩展欧几里得只要求两个数互质条件宽松许多。如果你在写竞赛题题目给了模数 1e97那用费马小定理最省事三步写完实现快速幂调用求逆元完事。但题目如果给了一个不确定的模数比如从输入里读一个上限、读一个 n那我会优先用扩展欧几里得它在运行时还能顺便判断逆元是否存在——gcd 不为 1 就返回 -1这个判断能力是费马小定理没有的。4.2 性能和稳定性对比从时间复杂度看费马小定理求逆元是 O(log p)扩展欧几里得是 O(log max(a, mod))。两者的对数底数和常数略有差异但整体都在对数级别单次调用差距很小。我实测过在 1e9 量级下两者单次调用耗时都可以忽略不计。真正有差别的是适用性和代码健壮性。费马小定理的代码非常短不容易写 bug但前提条件一旦不满足就静默出错可能返回一个看似合理的错误结果。扩展欧几里得的代码稍微复杂一点但它能反馈“是否存在逆元”让我在代码里显式处理无解情况这对工程代码来说很重要。给一个简单的对比表格对比维度费马小定理扩展欧几里得模数要求必须是质数仅要求与 a 互质核心操作快速幂 O(log p)辗转相除 O(log max(a, mod))代码长度较短略长是否能判断逆元存在不能直接判断能通过 gcd 判断典型场景1e97 等质数模数任意模数、需判断互质时数值溢出风险平方乘法需控制 mod 量级乘法次数少溢出风险低4.3 我个人的选型习惯我自己的习惯很简单竞赛里只要模数是固定质数无脑费马小定理因为代码短、好记、不容易出错。工程代码里模数可能是配置项甚至可能是变量我会用扩展欧几里得。另外如果代码里已经需要一个求 gcd 的函数那顺手写扩展欧几里得的成本更低因为它的骨架和 gcd 计算天然共享。这里提醒一句有些 Java 选手会把BigInteger.modInverse()当默认答案它底层用的其实就是扩展欧几里得的思路。但在算法竞赛里千万别依赖它因为 BigInteger 运算常数大而且很多人说不清它的时间开销。自己在模板里写一个轻量实现性能可控心里有底。5. 真实场景里的应用5.1 模意义下的除法最常见的应用就是模意义下的除法。假设题目让计算 (a / b) % MOD而 MOD 是质数 1e97你不能直接写(a / b) % MOD因为整数除法早就丢失了小数的精度。正确做法是long inv modInverseFermat(b, MOD); long ans a * inv % MOD;注意只有当 a 确确实实能被 b 整除时这个结果才等于真实的整数除法结果取模。但是在模运算的世界里我们其实不关心 a 能不能被 b 整除因为逆元定义下的“除法”本身就是乘上逆元这和我们平时说的实数除法不是一回事。这一点刚开始学的时候容易混淆多写几道题就习惯了。5.2 组合数计算预处理阶乘逆元组合数 C(n, k) n! / (k! * (n-k)!) 在模意义下直接用阶乘做除法是行不通的得先把分母转成逆元来乘。我看到很多模板里会一次性预处理所有阶乘和阶乘逆元static final int MOD 1_000_000_007; static long[] fac; static long[] invFac; static void initFactorials(int n) { fac new long[n 1]; invFac new long[n 1]; fac[0] 1; for (int i 1; i n; i) { fac[i] fac[i - 1] * i % MOD; } invFac[n] modInverseFermat(fac[n], MOD); for (int i n; i 1; i--) { invFac[i - 1] invFac[i] * i % MOD; } } static long C(int n, int k) { if (k 0 || k n) return 0; return fac[n] * invFac[k] % MOD * invFac[n - k] % MOD; }这里一个很妙的点就是只需要算一次fac[n]的逆元就能从后往前递推出所有invFac[i]。因为invFac[i] 1/i!而invFac[i-1] 1/(i-1)! i * invFac[i]。这个递推关系避免了为每个 i 单独做一次快速幂省下的时间相当可观。实测在 n 到达 1e6 级别的组合数预处理里这种写法能从 O(n log MOD) 优化到 O(n)。5.3 哈希处理和随机数分片逆元在非竞赛场景也有不少用处。比如做一致性哈希时有时候需要在模 N 的意义下做一个线性变换或缩放或者在设计自增 ID 的分片策略时需要通过模逆元把一段连续 ID 映射到另外一个看似打乱的序列。这些场景里模数往往不是质数用扩展欧几里得求逆元是最稳的选择因为它在合数模数下依然能工作。还有一个容易被忽略的点当你在一个分布式系统里需要给用户 ID 生成一个不可猜测的短串时可能会考虑“哈希 模逆元”的组合。但注意逆元的映射是一个线性映射并不具备加密强度讲究安全性的场景不能只靠它。这个属于用途边界的问题代码能跑通不等于业务上安全心里要有数。6. 常见问题与调试经验6.1 逆元不存在gcd 不是 1模运算里不是每个数都有逆元。如果 gcd(a, mod) ! 1那么无论用费马小定理还是扩展欧几里得都没法得到逆元。费马小定理在这种情况下会返回一个错误的“逆元”而且你自己很难察觉。扩展欧几里得就好一点因为它返回 gcd你只要判断返回值是不是 1 就能确认。我在代码里通常这么做long inv modInverseExgcd(a, mod); if (inv -1) { // 这里做异常处理而不是继续往下算 }6.2 结果出现负数扩展欧几里得解出来的 x 可能是负数这很常见。你直接用负数去做乘法再取模Java 的%运算符会保留负号导致结果负值。所以拿到 x 之后一定要做一次规范化long normalized (x % mod mod) % mod;这一步的原理很简单把 x 对 mod 取模后范围在 -(mod-1) 到 (mod-1) 之间加一个 mod 再取模就能保证结果落在 0 到 mod-1。这个操作在任何取模运算里都适用可以封装成工具方法省得每次手写。6.3 long 溢出不是所有模数都适合直接乘这是我在生产代码里踩过最深的坑。当模数比较小比如 1e9时long 里的乘法没问题但模数一旦逼近 1e10、1e12两个小于模数的数相乘就可能超过 long 的范围。很多人把这段代码搬到别的项目里改了个更大的模数就莫名其妙出负数就是因为溢出了。遇到这种场景最简单的方案是用快速乘法。它的原理和快速幂一模一样把乘法转成加法边加边模static long mulMod(long a, long b, long mod) { long res 0; a % mod; while (b 0) { if ((b 1) 1) { res (res a) % mod; } a (a a) % mod; b 1; } return res; }把快速幂里的res * a % mod换成mulMod(res, a, mod)把a * a % mod换成mulMod(a, a, mod)就得到一套防溢出的快速幂。代价是性能变慢但在大模数场景下只能这么干没有银弹。6.4 递归太深的问题扩展欧几里得的递归版本在普通场景下没问题但如果 a 和 mod 都是 BigInteger 那种超长整数递归深度就值得警惕了。不过 Java 的 BigInteger 自带modInverse真到那个量级我会直接用 BigInteger而不是自己维护一套递归。另外如果你在自己代码里频繁调用扩展欧几里得建议用非递归版至少不会有栈溢出的心理压力。6.5 线性递推求逆元的补充方案费马小定理和扩展欧几里得是两种“通用”方法但如果你需要一次求一堆数的逆元比如从 1 到 n 的所有逆元那还有更快的线性递推方式static long[] invs(int n, long mod) { long[] inv new long[n 1]; inv[1] 1; for (int i 2; i n; i) { inv[i] (mod - (mod / i) * inv[(int)(mod % i)] % mod) % mod; } return inv; }这个递推的推导过程有点绕但结论非常实用。mod / i是整除商mod % i小于 i所以inv[(int)(mod % i)]是前面已经算好的值。它只在 mod 是质数时成立且要求 n mod。这个方案我一般放在费马小定理和扩展欧几里得之后提因为它是“第三种思路”而且只在批量场景下才划算。7. 写在最后的实践心得我在实际做项目的时候对这两套方法的使用已经形成了肌肉记忆。固定质数模数就上费马小定理代码短到不可能写错碰到动态模数或者不确定模数就去调扩展欧几里得它给我的安全感来自那个能判断逆元是否存在的 gcd 返回值。这两套代码我已经封装进自己的基础工具类里每次开新项目都会带上。最后分享一个容易忽略的小技巧在写快速幂或者扩展欧几里得的时候把 mod 相关的操作单独抽成工具方法比如normalize(long x, long mod)和mulMod(long a, long b, long mod)这样既不破坏主流程的简洁又能在未来应对模数变大时快速改造。算法模板这东西平时花二十分钟打磨以后能帮你省下好几个小时的调试时间。
阅读完成 · 觉得有帮助？
