我的算法书 - 模逆元

一句话算法

模逆元就是模意义下的“倒数”，除以一个数可以改成乘它的逆元。

问题模型

给定整数 a 和模数 m，若存在整数 x 满足：

a \times x \equiv 1 \pmod m

则称 x 是 a 在模 m 意义下的逆元，记作 $a^{-1}$ 。

逆元存在的充要条件是：

\gcd(a,m)=1

核心直觉

在普通除法中：

\frac{A}{b}=A \times \frac{1}{b}

在模运算中不能直接除法，但如果能找到一个数 $b^{-1}$ ，使得：

b \times b^{-1} \equiv 1 \pmod m

那么就可以把除法改成乘法：

\frac{A}{b} \equiv A \times b^{-1} \pmod m

算法步骤

扩展欧几里得求单个逆元

要求 a 在模 m 下的逆元，就是解：

a x \equiv 1 \pmod m

等价于：

a x + m y = 1

这正是扩展欧几里得能求的形式。

步骤：

用 exgcd(a, m, x, y) 求出一组解。
若 gcd(a, m) != 1，逆元不存在。
否则 x 就是一个逆元。
用 (x % m + m) % m 调整到 [0, m-1]。

线性求 1…n 的逆元

当模数 p 是质数，并且要计算 1..n 所有逆元时，可以线性递推：

inv[i] = (p-\lfloor p/i \rfloor) \times inv[p\bmod i] \bmod p

初始条件：

inv[1] = 1

算法证明

为什么除法能变成乘逆元

设：

x \equiv \frac{A}{b} \pmod m

这表示：

b x \equiv A \pmod m

两边同乘 $b^{-1}$ ：

b^{-1} b x \equiv A b^{-1} \pmod m

因为 $b^{-1}b \equiv 1 \pmod m$ ，所以：

x \equiv A b^{-1} \pmod m

线性递推公式

令：

p = \left\lfloor \frac{p}{i} \right\rfloor i + (p \bmod i)

在模 p 意义下：

\left\lfloor \frac{p}{i} \right\rfloor i + (p \bmod i) \equiv 0

两边同乘 $i^{-1}(p\bmod i)^{-1}$ ：

\left\lfloor \frac{p}{i} \right\rfloor (p\bmod i)^{-1} + i^{-1} \equiv 0

移项得：

i^{-1} \equiv -\left\lfloor \frac{p}{i} \right\rfloor (p\bmod i)^{-1}

写成非负取模形式就是：

inv[i] = (p-\lfloor p/i \rfloor) \times inv[p\bmod i] \bmod p

复杂度分析

扩展欧几里得求单个逆元： $O(\log m)$ 。
线性求 1..n 逆元： $O(n)$ 。
空间复杂度：扩展欧几里得为 $O(1)$ ，线性递推为 $O(n)$ 。

代码实现

扩展欧几里得求逆元

C++

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

        #include <bits/stdc++.h>
using namespace std;

using i64 = long long;

i64 exgcd(i64 a, i64 b, i64 &x, i64 &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }

    i64 d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

i64 inverse(i64 a, i64 mod) {
    i64 x, y;
    i64 d = exgcd(a, mod, x, y);
    if (d != 1) return -1;
    return (x % mod + mod) % mod;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    i64 a, mod;
    cin >> a >> mod;

    cout << inverse(a, mod) << '\n';
    return 0;
}

Python

C++ 用 x, y 引用出参，Python 版 exgcd 返回 (d, x, y)；调用方保证 $a, b \geqslant 0$ （取模语义差异见文件头）。

python

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

        # 扩展欧几里得：返回 (d, x, y)，满足 a * x + b * y = d = gcd(a, b)。
# C++ 用 i64& x, i64& y 出参，Python 没有引用出参，改为返回三元组，顺序为 (d, x, y)。
# 调用方保证 a, b >= 0：C++ 的 % 是向零截断取模，Python 是向下取模，负数输入下
# 两者的 (x, y) 会不同（|d| 相同）。
# C++ 的 long long 在 a * x + b * y 处可能溢出；Python int 任意精度。

type Triple = tuple[int, int, int]  # (gcd, x, y)


def exgcd(a: int, b: int) -> Triple:
    if b == 0:
        # 递归基：gcd(a, 0) = a，取 x = 1, y = 0 即可。
        return a, 1, 0

    # 由 b * x' + (a % b) * y' = d 及 a % b = a - (a // b) * b 反推：
    # a * y' + b * (x' - (a // b) * y') = d，所以新系数是 (y', x' - (a // b) * y')。
    d, x_next, y_next = exgcd(b, a % b)
    return d, y_next, x_next - (a // b) * y_next


def inverse(a: int, mod: int) -> int:
    d, x, _ = exgcd(a, mod)
    if d != 1:
        return -1  # a 与 mod 不互质时逆元不存在
    # x 可能是负数，先对 mod 取模再调整到 [0, mod)。
    return (x % mod + mod) % mod

线性求逆元

C++

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

        #include <bits/stdc++.h>
using namespace std;

using i64 = long long;

vector<i64> linear_inverse(int n, i64 mod) {
    vector<i64> inv(n + 1);
    inv[1] = 1;
    for (int i = 2; i <= n; i++) {
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    }
    return inv;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    i64 mod;
    cin >> n >> mod;

    auto inv = linear_inverse(n, mod);
    for (int i = 1; i <= n; i++) {
        cout << inv[i] << '\n';
    }

    return 0;
}

Python

python

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

        # 线性求 1..n 每个数在模 mod 下的逆元，返回长度 n + 1 的数组 inv（1 下标，inv[0] 无意义）。
# 递推：inv[i] = (mod - mod / i) * inv[mod % i] % mod。
# 调用方保证 1 <= n < mod 且 mod 是质数：这样 mod % i < i <= n，inv[mod % i] 一定已经算好。
# C++ 的 long long 在 (mod - mod / i) * inv[mod % i] 处可能溢出；Python int 任意精度。

type InvTable = list[int]  # inv[i] 是 i 在模 mod 下的逆元


def linear_inverse(n: int, mod: int) -> InvTable:
    inv: InvTable = [0] * (n + 1)
    inv[1] = 1
    for i in range(2, n + 1):
        # mod / i 是整除；先算 mod % i 的逆元，再用 mod - mod / i 修正符号。
        inv[i] = (mod - mod // i) * inv[mod % i] % mod
    return inv

测试用例

扩展欧几里得求逆元：

3 11

输出：

因为 $3 \times 4 \equiv 1 \pmod {11}$ 。

线性求逆元：

5 7

输出：

应用分类详解

模逆元的本质是把模意义下的除法转成乘法。凡是题目要求“取模后除以某个数”，都要想到逆元。

一、单次模除法

典型模式： 求 a / b mod m。

识别信号： 出现“答案对 m 取模”，公式中又有除法。

核心建模： 先求 b 的逆元，再计算 a * inv(b) % m。

应用场景	经典题目	核心思路
单个逆元	51Node-1256	exgcd 求解 `ax + my = 1`
逆元模板	luogu-P3811	线性递推求 `1..n` 所有逆元

二、组合数取模

典型模式： 求 $C(n,m) \bmod p$ 。

识别信号： 公式中有阶乘相除： $\frac{n!}{m!(n-m)!}$ 。

核心建模： 预处理阶乘和阶乘逆元，把除法改成乘逆元。

三、概率与期望取模

典型模式： 概率是分数，但题目要求模意义输出。

识别信号： 出现“若答案为 P/Q，输出 P * Q^{-1} mod M”。

核心建模： 分母用逆元消掉。

经典例题

1. luogu-P3811

乘法逆元模板题。要求在线性时间内输出 1..n 的逆元。

2. 51Node-1256

单个逆元题。适合练习扩展欧几里得求逆元。

3. 组合数取模模板题

重点是把除以阶乘转成乘阶乘逆元。

参考

本书扩展欧几里得章节：math/numberTheory/exgcd/index.md