【算法基础篇】（四十七）乘法逆元终极宝典：从模除困境到三种解法全解析-平芜编程栈

前言

在算法竞赛的模运算场景中，“除法取模” 始终是令人头疼的难题 —— 同余式不满足除法封闭性，直接计算(a÷b)modp会导致结果错误。而乘法逆元正是破解这一困境的 “密钥”，它能将除法转化为乘法，让模运算中的除法操作合法可行。本文将从逆元的定义与核心作用出发，详解费马小定理、扩展欧几里得算法、线性递推三种主流求逆元方法，手把手教你掌握从单逆元求解到批量预处理的全流程，让你在模运算中彻底摆脱除法困扰。下面就让我们正式开始吧！

前言

在算法竞赛的模运算场景中，“除法取模” 始终是令人头疼的难题 —— 同余式不满足除法封闭性，直接计算(a÷b)modp会导致结果错误。而乘法逆元正是破解这一困境的 “密钥”，它能将除法转化为乘法，让模运算中的除法操作合法可行。本文将从逆元的定义与核心作用出发，详解费马小定理、扩展欧几里得算法、线性递推三种主流求逆元方法，手把手教你掌握从单逆元求解到批量预处理的全流程，让你在模运算中彻底摆脱除法困扰。下面就让我们正式开始吧！

一、乘法逆元的核心概念：为什么需要逆元？

1.1 逆元的定义

若整数a与模数m互质（即gcd(a,m)=1），且存在整数x使得a × x ≡ 1(mod m)，则称x是a模m的乘法逆元，记作a−1（注意此处不是倒数，而是模意义下的逆元）。

举个直观例子：3×7=21≡1(mod10)，因此 7 是 3 模 10 的乘法逆元，反过来 3 也是 7 模 10 的乘法逆元。

1.2 逆元的核心作用：除法转乘法

逆元的最大价值在于将模运算中的除法转化为乘法。对于算式(b÷a)mod p，由于直接除法不合法，我们可以用a的逆元a−1替代除法，转化为(b×a−1)mod p，结果与原算式等价。

示例验证：

计算(25÷5)mod3：

直接计算：25÷5=5，5 mod 3=2；
用逆元计算：5 模 3 的逆元是 2（因为5×2=10≡1(mod3)），则(25×2)mod3=50mod3=2，结果一致。

为什么需要逆元？

在算法竞赛中，很多题目要求结果对大质数（如1e9+7）取模，而计算过程中常涉及组合数、分式求和等含除法的场景。如果直接计算除法再取模，会因精度丢失或同余性质破坏导致错误，逆元则完美解决了这一问题。

1.3 逆元存在的条件

乘法逆元存在的充要条件是：a与m互质（gcd(a,m)=1）。若a与m不互质，则不存在逆元。

反例：

求 2 模 4 的逆元：gcd(2,4)=2≠1，不存在整数x使得2x≡1(mod 4)（2x 的结果只能是 0、2 mod 4），因此逆元不存在。

二、三种求逆元的方法：从单逆元到批量预处理

2.1 方法一：费马小定理 + 快速幂（适用于质数模数）

定理基础

费马小定理指出：若p为质数，且a与p互质，则。

对定理变形可得：。根据逆元定义，就是a模p的乘法逆元。

适用条件

模数p必须是质数；
a与p互质（由于p是质数，只需a不是p的倍数即可）。

核心工具：快速幂算法

快速幂算法能在O(logb)时间内计算，是实现费马小定理求逆元的关键。

C++ 实现（费马小定理 + 快速幂）

#include <iostream> using namespace std; typedef long long LL; // 快速幂计算 (a^b) mod p LL qpow(LL a, LL b, LL p) { LL ret = 1; a = a % p; // 底数取模，避免溢出 while (b > 0) { if (b & 1) { // 二进制位为1时，结果乘当前底数 ret = ret * a % p; } a = a * a % p; // 底数平方 b >>= 1; // 指数右移一位 } return ret; } // 费马小定理求逆元：p必须是质数，且a与p互质 LL mod_inv_fermat(LL a, LL p) { return qpow(a, p - 2, p); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); LL a = 5, p = 1e9 + 7; // p是质数 LL inv = mod_inv_fermat(a, p); cout << a << "模" << p << "的逆元为：" << inv << endl; // 验证：5 * 200000001 mod 1e9+7 = 1（200000001是5模1e9+7的逆元） return 0; }

代码分析

时间复杂度：O(logp)，快速幂的循环次数为p的二进制位数，对于p=1e9+7，仅需 30 次左右循环；
适用场景：单逆元求解，且模数为质数（竞赛中最常见的场景，如1e9+7、998244353等）；
优势：代码简洁，实现难度低，效率高。

2.2 方法二：扩展欧几里得算法（适用于任意互质模数）

算法基础

扩展欧几里得算法（exgcd）的核心功能是求解二元一次不定方程ax+by=gcd(a,b)。当a与m互质时，gcd(a,m)=1，方程转化为ax+my=1。对该方程取模m，可得ax≡1(mod m)，此时x的最小正整数解就是a模m的逆元。

适用条件

a与m互质（无需m是质数）；
适用于任意模数（质数、合数均可）。

C++ 实现（扩展欧几里得算法求逆元）

#include <iostream> using namespace std; typedef long long LL; // 扩展欧几里得算法：返回gcd(a,b)，并通过引用返回方程ax+by=gcd(a,b)的特解(x,y) LL exgcd(LL a, LL b, LL& x, LL& y) { if (b == 0) { x = 1, y = 0; return a; } LL x1, y1, d; d = exgcd(b, a % b, x1, y1); // 推导当前层特解 x = y1; y = x1 - (a / b) * y1; return d; } // 扩展欧几里得算法求逆元：a与m互质时返回逆元，否则返回-1 LL mod_inv_exgcd(LL a, LL m) { LL x, y; LL d = exgcd(a, m, x, y); if (d != 1) { return -1; // a与m不互质，无逆元 } // 转化为最小正整数解 return (x % m + m) % m; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 示例1：模数为质数 LL a1 = 5, m1 = 1e9 + 7; LL inv1 = mod_inv_exgcd(a1, m1); cout << a1 << "模" << m1 << "的逆元：" << inv1 << endl; // 输出200000001 // 示例2：模数为合数（a与m互质） LL a2 = 3, m2 = 10; LL inv2 = mod_inv_exgcd(a2, m2); cout << a2 << "模" << m2 << "的逆元：" << inv2 << endl; // 输出7 // 示例3：a与m不互质，无逆元 LL a3 = 2, m3 = 4; LL inv3 = mod_inv_exgcd(a3, m3); cout << a3 << "模" << m3 << "的逆元：" << inv3 << endl; // 输出-1 return 0; }

代码分析

时间复杂度：O(logmin(a,m))，与欧几里得算法一致，效率极高；
适用场景：单逆元求解，尤其是模数为合数的场景（弥补了费马小定理的局限性）；
优势：适用范围广，无需模数是质数，是求逆元的通用方法。

2.3 方法三：线性递推法（适用于批量求逆元）

算法原理

当需要求解1∼n中所有数模p的逆元时，线性递推法能在O(n)时间内完成预处理，效率远超逐个求解。

核心递推公式（p为质数）：

公式推导

设p=q×i+r（0<r<i），则r=p mod i。对等式取模p得：q×i+r ≡ 0(mod p)，两边乘inv[i]×inv[r]：q×inv[r]+inv[i] ≡ 0(mod p)，整理得：inv[i] ≡ −q×inv[r](mod p)；由于q=p/i，代入得：inv[i]=(p−p/i)∗inv[p mod i] mod p（加p是为了保证结果为正）

适用条件

模数p必须是质数；
需批量求解1∼n的逆元（n<p）。

C++ 实现（线性递推求批量逆元）

#include <iostream> using namespace std; typedef long long LL; const int MAXN = 3e6 + 10; // 根据需求调整最大范围 LL inv[MAXN]; // 线性递推预处理1~n模p的逆元（p为质数） void pre_inv(LL n, LL p) { inv[1] = 1; // 1的逆元是1 for (int i = 2; i <= n; ++i) { inv[i] = (p - p / i) * inv[p % i] % p; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); LL n = 10, p = 13; // p是质数 pre_inv(n, p); cout << "1~" << n << "模" << p << "的逆元：" << endl; for (int i = 1; i <= n; ++i) { cout << i << "的逆元：" << inv[i] << endl; } /* 输出结果： 1的逆元：1 2的逆元：7 3的逆元：9 4的逆元：10 5的逆元：8 6的逆元：11 7的逆元：2 8的逆元：5 9的逆元：3 10的逆元：4 */ return 0; }

代码分析

时间复杂度：O(n)，线性遍历一次即可完成所有逆元的计算；
适用场景：组合数预处理、多组分式求和等需要频繁使用1∼n逆元的场景；
优势：批量处理效率极高，空间开销仅为O(n)，对于n=1e6仅需 4MB 内存（int 数组）。

三、三种方法对比：如何选择合适的求逆元方式？

方法	适用条件	时间复杂度	核心优势	局限性
费马小定理 + 快速幂	模数 p 为质数，a 与 p 互质	O(logp)	代码简洁，实现简单，单逆元高效	仅适用于质数模数
扩展欧几里得算法	a 与 m 互质（m 可为任意整数）	O(logm)	通用型强，支持合数模数	单逆元求解，批量效率低
线性递推法	模数 p 为质数，批量求 1~n 逆元	O(n)	批量处理速度极快，空间开销小	仅适用于质数模数和批量场景

选择策略：

单逆元 + 质数模数：优先用费马小定理 + 快速幂；
单逆元 + 合数模数：必须用扩展欧几里得算法；
批量逆元 + 质数模数：优先用线性递推法；
若 a 与 m 不互质：逆元不存在，需结合题目场景特殊处理（如分子分母同乘公因数约分后再求逆元）。

四、实战例题 1：洛谷 P3811 【模板】模意义下的乘法逆元

题目链接：https://www.luogu.com.cn/problem/P3811

4.1 题目分析

题目描述：给定n和p，求1∼n中所有整数在模p意义下的乘法逆元（p为质数）。

输入描述：一行两个正整数n和p。

输出描述：输出n行，第i行表示i在模p下的逆元。

示例输入：10 13 → 输出与线性递推示例一致。

核心思路：使用线性递推法，O(n)时间预处理所有逆元，效率最高。

4.2 C++ 实现

#include <iostream> using namespace std; typedef long long LL; const int MAXN = 3e6 + 10; LL inv[MAXN]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); LL n, p; scanf("%lld%lld", &n, &p); inv[1] = 1; for (int i = 2; i <= n; ++i) { inv[i] = (p - p / i) * inv[p % i] % p; } for (int i = 1; i <= n; ++i) { printf("%lld\n", inv[i]); } return 0; }

4.3 优化说明

输入输出优化：使用scanf和printf替代cin和cout，提升大数据量下的读写速度；
空间优化：对于n=3e6，inv数组占用约 12MB（LL 类型），完全符合竞赛内存限制；
时间优化：线性递推无冗余操作，n=3e6仅需几毫秒即可完成。

五、实战例题 2：牛客网【模板】逆元

题目链接：https://ac.nowcoder.com/acm/problem/226824

5.1 题目分析

题目描述：求x模p意义下的逆元，若不存在则输出−1。

输入描述：第一行一个整数T，每组数据一行两个整数x和p（2≤x<p≤1e9）。

输出描述：每组数据输出逆元或−1。

示例输入：24 82 1000000007

示例输出：-1500000004

核心思路：

由于p可能是质数或合数，需用扩展欧几里得算法（通用方法）；
先判断x与p是否互质，若不互质输出−1，否则求解逆元。

5.2 C++ 实现

#include <iostream> using namespace std; typedef long long LL; LL exgcd(LL a, LL b, LL& x, LL& y) { if (b == 0) { x = 1, y = 0; return a; } LL x1, y1, d; d = exgcd(b, a % b, x1, y1); x = y1; y = x1 - (a / b) * y1; return d; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin >> T; while (T--) { LL x, p; cin >> x >> p; LL x0, y0, d; d = exgcd(x, p, x0, y0); if (d != 1) { cout << -1 << endl; } else { // 转化为最小正整数解 cout << (x0 % p + p) % p << endl; } } return 0; }

5.3 代码验证

第一组输入：4 8 → gcd(4,8)=4=1，无逆元，输出−1；
第二组输入：2 1e9+7 → gcd(2,1e9+7)=1，逆元为500000004（2×500000004=1000000008≡1(mod1e9+7)），输出500000004。

六、常见误区与避坑指南

6.1 逆元存在条件判断错误

误区：忽略a与m互质的条件，直接求解逆元；
避坑：先用欧几里得算法计算gcd(a,m)，若结果不为 1，直接判定无逆元。

6.2 模数类型混淆

误区：用费马小定理求解合数模数的逆元；
反例：a=3，m=10（合数），若误用费马小定理，310−2=38=6561≡1(mod10)，恰好得到逆元 7，但这是巧合，多数情况下会出错；
避坑：费马小定理仅适用于质数模数，合数模数必须用扩展欧几里得算法。

6.3 结果为负未调整

误区：扩展欧几里得算法求出的特解可能为负，直接输出；
避坑：用(xmodm+m)modm将结果转化为最小正整数解。

6.4 数据溢出问题

误区：快速幂或扩展欧几里得算法中使用 int 类型，导致乘法溢出；
避坑：所有变量统一使用 long long 类型，尤其是模数为1e9+7时，中间结果可能超过 int 范围。

6.5 线性递推公式记错

误区：将递推公式记为inv[i]=(p/i)∗inv[pmodi]modp，遗漏负号；
避坑：牢记公式为inv[i]=(p−p/i)∗inv[pmodi]modp，加p是为了保证结果为正。

总结

乘法逆元是模运算中处理除法的核心工具，三种求解方法各有适用场景，关键在于根据模数类型（质数 / 合数）和需求（单逆元 / 批量逆元）选择合适的方法。
如果在学习过程中遇到具体题目无法解决，或想了解逆元在更复杂场景（如扩展中国剩余定理）中的应用，可以随时留言交流。后续将持续更新数论进阶内容，敬请关注！

前言

目录

前言

一、乘法逆元的核心概念：为什么需要逆元？

1.1 逆元的定义

1.2 逆元的核心作用：除法转乘法

示例验证：

为什么需要逆元？

1.3 逆元存在的条件

反例：

二、三种求逆元的方法：从单逆元到批量预处理

2.1 方法一：费马小定理 + 快速幂（适用于质数模数）

定理基础

适用条件

核心工具：快速幂算法

C++ 实现（费马小定理 + 快速幂）

代码分析

2.2 方法二：扩展欧几里得算法（适用于任意互质模数）

算法基础

适用条件

C++ 实现（扩展欧几里得算法求逆元）

代码分析

2.3 方法三：线性递推法（适用于批量求逆元）

算法原理

公式推导

适用条件

C++ 实现（线性递推求批量逆元）

代码分析

三、三种方法对比：如何选择合适的求逆元方式？

选择策略：

四、实战例题 1：洛谷 P3811 【模板】模意义下的乘法逆元

4.1 题目分析

4.2 C++ 实现

4.3 优化说明

五、实战例题 2：牛客网【模板】逆元

5.1 题目分析

5.2 C++ 实现

5.3 代码验证

六、常见误区与避坑指南

6.1 逆元存在条件判断错误

6.2 模数类型混淆

6.3 结果为负未调整

6.4 数据溢出问题

6.5 线性递推公式记错

总结

TCC-G15：戴尔游戏本散热控制的全新革命

如何快速掌握LeagueAkari：英雄联盟玩家的10个必学实用技巧

NCM音频解密技术详解：ncmdump核心原理与实战应用

qmcdump音频解密工具终极指南：解锁QQ音乐加密文件

3大突破：开源AI编程工具OpenCode的实战深度测评

Qwen_Image_Cute_Animal性能测试：长时运行的稳定性分析