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

前言

在算法竞赛的模运算场景中，“除法取模” 始终是令人头疼的难题 —— 同余式不满足除法封闭性，直接计算(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 数组）。

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

选择策略：

1. 单逆元 + 质数模数：优先用费马小定理 + 快速幂；
2. 单逆元 + 合数模数：必须用扩展欧几里得算法；
3. 批量逆元 + 质数模数：优先用线性递推法；
4. 若 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是为了保证结果为正。

总结

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