模乘逆元-未完纪

Last update:
April 10, 2026

Translated

From: e-maxx.ru

定义

整数 $a$ 的模乘逆元是一个整数 $x$，使得 $a \cdot x$ 在模 $m$ 意义下与 $1$ 同余。形式化地说，我们要寻找满足下式的整数 $x$： modular multiplicative inverse

$$a \cdot x \equiv 1 \mod m.$$

也可以将 $x$ 简记为 $a^{-1}$。

模逆元并不总是存在。例如 $m=4$、$a=2$，检查模 $m$ 的所有可能取值，就会发现没有满足上述等式的 $a^{-1}$。可以证明：模逆元存在，当且仅当 $a$ 与 $m$ 互质，即 $\gcd(a,m)=1$。

本文介绍逆元存在时的两种求法，以及在线性时间内求出所有数的逆元的方法。

使用扩展欧几里得算法求模逆元

考虑以下方程，其中 $x$ 和 $y$ 为未知数：

$$a \cdot x + m \cdot y = 1$$

这是一个二元线性丢番图方程。链接文章说明，当 $\gcd(a,m)=1$ 时，方程存在解，可以通过扩展欧几里得算法求得。注意，这也正是模逆元存在的条件。 Linear Diophantine equation in two variables extended Euclidean algorithm

对方程两边取模 $m$，可以消去 $m \cdot y$，得到：

$$a \cdot x \equiv 1 \mod m$$

因此，$a$ 的模逆元就是 $x$。

实现如下：

int x, y;
int g = extended_euclidean(a, m, x, y);
if (g != 1) {
    cout << "No solution!";
}
else {
    x = (x % m + m) % m;
    cout << x << endl;
}

注意对 x 的处理。扩展欧几里得算法求出的 x 可能为负数，因此 x % m 也可能为负。先加上 m，再取模，就能得到规范的非负结果。

使用二进制快速幂求模逆元

另一种方法利用欧拉定理：当 $a$ 与 $m$ 互质时，下面的同余式成立：

$$a^{\phi (m)} \equiv 1 \mod m$$

$\phi$ 是欧拉函数。再次注意，$a$ 与 $m$ 互质，也是模逆元存在的条件。 Euler’s Totient function

如果 $m$ 是素数，这可以简化为费马小定理： Fermat’s little theorem

$$a^{m – 1} \equiv 1 \mod m$$

在以上等式两边乘以 $a^{-1}$，得到：

对于一般的模数 $m$（但 $a$ 与 $m$ 必须互质）：$a^{\phi(m)-1} \equiv a^{-1} \mod m$。
对于素数模数 $m$：$a^{m-2} \equiv a^{-1} \mod m$。

由此，可以使用二进制快速幂算法，在 $O(\log m)$ 时间内求出模逆元。 binary exponentiation algorithm

虽然这种方法比前面的方法更容易理解，但当 $m$ 不是素数时，需要计算欧拉函数，这涉及对 $m$ 进行因数分解，可能很困难。如果 $m$ 的素因数分解已知，这种方法的复杂度就是 $O(\log m)$。

使用欧几里得除法求素数模数下的逆元

给定素数模数 $m>a$（也可以先取模，一步使 $a$ 变小），根据欧几里得除法： Euclidean Division

$$m = k \cdot a + r$$

其中 $k=\lfloor m/a \rfloor$，$r=m\bmod a$，于是：

$$
\begin{align*}
& \implies & 0 & \equiv k \cdot a + r & \mod m \\
& \iff & r & \equiv -k \cdot a & \mod m \\
& \iff & r \cdot a^{-1} & \equiv -k & \mod m \\
& \iff & a^{-1} & \equiv -k \cdot r^{-1} & \mod m
\end{align*}
$$

当 $m$ 不是素数时，这个推导不成立，因为一般情况下 $a^{-1}$ 存在并不意味着 $r^{-1}$ 存在。例如用上述公式计算模 $12$ 的 $5^{-1}$，希望得到 $5$，因为 $5\cdot5\equiv1\bmod12$。但 $12=2\cdot5+2$，所以 $k=2$、$r=2$，而 $2$ 在模 $12$ 下没有逆元。

如果模数是素数，所有 $0

int inv(int a) {
  return a <= 1 ? a : m - (long long)(m/a) * inv(m % a) % m;
}

这个递归的精确时间复杂度尚不明确，介于 $O(\log m/\log\log m)$ 与 $O(m^{1/3-2/177+\epsilon})$ 之间。参见论文《On the length of Pierce expansions》。实际中，这个实现很快。例如模数为 $10^9+7$ 时，原文报告它总能在不到 50 次迭代内完成。 On the length of Pierce expansions

使用这个公式，也可以在 $O(m)$ 时间内预计算 $[1,m-1]$ 范围内每个数的模逆元。

inv[1] = 1;
for(int a = 2; a < m; ++a)
    inv[a] = m - (long long)(m/a) * inv[m%a] % m;

求数组中所有数的模 $m$ 逆元

给定一个数组，要求所有元素的模逆元，并假定所有元素都有逆元。无需逐个求逆元，可以用不包括当前元素的前缀积和后缀积扩展分式，最终只需要计算一次逆元。

$$
\begin{align}
x_i^{-1} &= \frac{1}{x_i} = \frac{\overbrace{x_1 \cdot x_2 \cdots x_{i-1}}^{\text{prefix}_{i-1}} \cdot ~1~ \cdot \overbrace{x_{i+1} \cdot x_{i+2} \cdots x_n}^{\text{suffix}_{i+1}}}{x_1 \cdot x_2 \cdots x_{i-1} \cdot x_i \cdot x_{i+1} \cdot x_{i+2} \cdots x_n} \\
&= \text{prefix}_{i-1} \cdot \text{suffix}_{i+1} \cdot \left(x_1 \cdot x_2 \cdots x_n\right)^{-1}
\end{align}
$$

代码先建立前缀积数组（不包括当前元素，从乘法单位元开始），计算所有数乘积的逆元，再乘以前缀积和后缀积。后缀积通过从后向前遍历得到。

std::vector<int> invs(const std::vector<int> &a, int m) {
    int n = a.size();
    if (n == 0) return {};
    std::vector<int> b(n);
    int v = 1;
    for (int i = 0; i != n; ++i) {
        b[i] = v;
        v = static_cast<long long>(v) * a[i] % m;
    }
    int x, y;
    extended_euclidean(v, m, x, y);
    x = (x % m + m) % m;
    for (int i = n - 1; i >= 0; --i) {
        b[i] = static_cast<long long>(x) * b[i] % m;
        x = static_cast<long long>(x) * a[i] % m;
    }
    return b;
}