# 乘法逆元：把取模中的“除法”变成“乘法”

在 OI 里，很多题都会要求答案对一个数取模，比如：

$ans \bmod 998244353$

或者：

$ans \bmod 1000000007$

这时如果式子里有除法，比如：

$\frac{a}{b} \bmod MOD$

我们通常不能直接写：

```cpp
ans = a / b % MOD;
```

因为取模之后，普通除法经常会失效。

正确思路是：

- 不直接除以 $b$
- 而是乘上 $b$ 在模 $MOD$ 意义下的乘法逆元

也就是把：

$\frac{a}{b}$

改成：

$a \times b^{-1}$

其中 $b^{-1}$ 满足：

$b \times b^{-1} \equiv 1 \pmod {MOD}$

这个 $b^{-1}$ 就叫做 $b$ 在模 $MOD$ 意义下的 **乘法逆元**。

---

## 为什么取模下不能随便除

在普通整数里：

$6 \div 3 = 2$

当然没问题；但在取模的操作里，我们关心的是“余数”。比如模 $5$ 操作有：

$6 \equiv 1 \pmod 5$

如果你先除再取模：

$6 \div 3 = 2$

得到的是 $2$。但如果你先把 $6$ 变成余数：

$6 \equiv 1 \pmod 5$

那问题就变成：

$1 \div 3 \pmod 5$

这时“除以 $3$”到底是什么意思？

在模意义下，我们不把它理解成普通除法，而是理解成：

乘上一个数 $x$，让 $3x$ 的余数等于 $1$。

也就是找：

$3x \equiv 1 \pmod 5$

试一下可以发现：

$3 \times 2 = 6 \equiv 1 \pmod 5$

所以：

$3^{-1} \equiv 2 \pmod 5$

于是：

$1 \div 3 \equiv 1 \times 2 \equiv 2 \pmod 5$

这次结果刚好还是 $2$，但关键是：**取模意义下的除法，本质上是乘逆元**。

---

## 乘法逆元

如果有两个整数 $a$ 和 $x$，满足：

$a \times x \equiv 1 \pmod m$

那么 $x$ 就叫做 $a$ 在模 $m$ 意义下的乘法逆元。

通常写成：

$x \equiv a^{-1} \pmod m$

也就是：

$a \times a^{-1} \equiv 1 \pmod m$

也就是说：

- 普通数学里，$a$ 的倒数是 $\frac{1}{a}$
- 取模数学里，$a$ 的“倒数”就是 $a^{-1}$
- 普通除法里的除以 $a$，在取模里就变成乘 $a^{-1}$

所以：

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

---

## 逆元的存在性

逆元不一定存在。我们说 $a$ 在模 $m$ 意义下有逆元，当且仅当：

$\gcd(a,m)=1$

也就是说，$a$ 和 $m$ 必须互质。

比如说 $3$ 和 $5$ 互质，所以 $3$ 在模 $5$ 意义下有逆元；这是因为：

$3 \times 2 \equiv 1 \pmod 5$

所以：

$3^{-1} \equiv 2 \pmod 5$

再举个没有逆元的例子：

$2$ 和 $6$ 不互质，因为：

$\gcd(2,6)=2$

我们想找：

$2x \equiv 1 \pmod 6$

但 $2x$ 一定是偶数，它对 $6$ 取模后只可能是：$0,2,4$，不可能得到 $1$。

所以 $2$ 在模 $6$ 意义下没有逆元。

---

## 为什么算法竞赛里经常能用逆元

因为很多题的模数是质数，比如：

- $998244353$
- $1000000007$
- $1000000009$

如果 $MOD$ 是质数，那么只要 $a$ 不是 $MOD$ 的倍数，就一定有：

$\gcd(a,MOD)=1$

也就是说，大多数时候我们要求的分母都有逆元。

于是组合数、概率、期望、DP 计数里的除法，都可以写成乘逆元。

例如：

$\binom{n}{k}=\frac{n!}{k!(n-k)!}$

在模 $MOD$ 意义下可以写成：

$\binom{n}{k}\equiv n! \times (k!)^{-1} \times ((n-k)!)^{-1} \pmod {MOD}$

这就是组合数预处理里经常出现 `fac` 和 `ifac` 的原因。

---

## 方法一：快速幂求逆元

这是最常用的方法。

前提：

- $MOD$ 是质数
- $a$ 不是 $MOD$ 的倍数

根据费马小定理：

$a^{MOD-1}\equiv 1 \pmod {MOD}$

把左边拆开看：

$a^{MOD-1}=a\times a^{MOD-2}$

所以：

$a^{MOD-2}\equiv a^{-1} \pmod {MOD}$

也可以写成：

$a^{-1}\equiv a^{MOD-2} \pmod {MOD}$

也就是说，只要求：

$a^{MOD-2} \bmod MOD$

就能得到 $a$ 的逆元。

快速幂代码如下：

```cpp
using ll = long long;

ll qpow(ll a, ll b, ll mod) {
    ll res = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

ll inv(ll a, ll mod) {
    return qpow(a, mod - 2, mod);
}
```

使用例子：

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

const int MOD = 998244353;

int main() {
    long long a = 3;
    long long inv_a = inv(a, MOD);
    cout << inv_a << '\n';
    return 0;
}
```

复杂度：

$O(\log MOD)$

这种写法简单、稳定，比赛里常用。

---

## 方法二：扩展欧几里得求逆元

上面的快速幂求逆元法依赖 $MOD$ 是质数。如果 $MOD$ 不一定是质数，但 $a$ 和 $MOD$ 互质，也可以用扩展欧几里得算法。

因为当：

$\gcd(a,m)=1$

根据裴蜀定理，一定存在整数 $x$ 和 $y$，使得：

$ax+my=1$

两边对 $m$ 取模：

$ax+my\equiv 1 \pmod m$

因为：

$my\equiv 0 \pmod m$

所以：

$ax\equiv 1 \pmod m$

这说明 $x$ 就是 $a$ 在模 $m$ 意义下的逆元。

代码如下：

```cpp
using ll = long long;

ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll x1, y1;
    ll g = exgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - a / b * y1;
    return g;
}

ll inv(ll a, ll mod) {
    ll x, y;
    ll g = exgcd(a, mod, x, y);
    if (g != 1) return -1; // 不存在逆元
    x %= mod;
    if (x < 0) x += mod;
    return x;
}
```

复杂度：

$O(\log MOD)$

这个方法的优点是：

- 模数不要求是质数
- 只要 $a$ 和 $MOD$ 互质，就能求

---

## 方法三：线性递推求一整段逆元

有时我们不是只求一个数的逆元，而是要求：

$1^{-1},2^{-1},3^{-1},\dots,n^{-1}$

如果 $MOD$ 是质数，并且 $1 \le i < MOD$，可以用线性递推：

$inv[1]=1$

$inv[i]=(MOD-\lfloor\frac{MOD}{i}\rfloor)\times inv[MOD\bmod i]\bmod MOD$

代码如下：

```cpp
const int N = 1000000;
const int MOD = 998244353;

long long inv[N + 5];

void init_inv() {
    inv[1] = 1;
    for (int i = 2; i <= N; ++i) {
        inv[i] = 1LL * (MOD - MOD / i) * inv[MOD % i] % MOD;
    }
}
```

复杂度：$O(n)$

它适合一次性预处理很多个逆元。

---

## 阶乘逆元与组合数

组合数是逆元最常见的应用之一。

我们知道：

$\binom{n}{k}=\frac{n!}{k!(n-k)!}$

在模意义下：

$\binom{n}{k}\equiv fac[n]\times ifac[k]\times ifac[n-k]\pmod {MOD}$

其中：

- $fac[i]$ 表示 $i!$
- $ifac[i]$ 表示 $(i!)^{-1}$

预处理方式如下：

```cpp
const int N = 1000000;
const int MOD = 998244353;

long long fac[N + 5], ifac[N + 5];

long long qpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

void init_comb() {
    fac[0] = 1;
    for (int i = 1; i <= N; ++i) {
        fac[i] = fac[i - 1] * i % MOD;
    }

ifac[N] = qpow(fac[N], MOD - 2);
    for (int i = N; i >= 1; --i) {
        ifac[i - 1] = ifac[i] * i % MOD;
    }
}

long long C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fac[n] * ifac[k] % MOD * ifac[n - k] % MOD;
}
```

注意这个模板默认 $MOD$ 是质数，并且通常要求预处理范围里的阶乘不要变成 $0$，也就是常见场景下有 $N<MOD$。

如果 $n \ge MOD$，普通阶乘逆元模板可能失效，需要考虑 Lucas 定理等其他方法。

这里有一个很重要的小技巧：

不用对每个 $fac[i]$ 都快速幂一次。

只需要先求：

$ifac[N]=(fac[N])^{-1}$

然后倒着推：

$ifac[i-1]=ifac[i]\times i$

这样预处理组合数的复杂度就是：$O(n+\log MOD)$

查询一次组合数：$O(1)$

---

## 合数模数时要注意

不是所有模数都适合直接求逆元。比如：

$10000=2^4\times 5^4$

它是合数，这时 $2$、$4$、$5$、$10$ 等数都没有模 $10000$ 的逆元，因为它们和 $10000$ 不互质。

所以遇到合数模数时，不能看到除法就直接写：

```cpp
ans = ans * inv(x) % MOD;
```

必须要先判断：

$\gcd(x,MOD)=1$

如果不互质，就不能直接用逆元处理这个除法。

常见处理方式有：

- 把和 $MOD$ 有公共因子的部分单独拆出来
- 对剩下互质的部分求逆元
- 或者换用更适合该题的数学方法，比如中国剩余定理、质因数分解、Lucas 定理等

这类题通常考的通常是你是否知道**逆元存在**的必要前提！

---

## 常见错误

### 错误一：模数不是质数还用费马小定理

费马小定理要求模数是质数。如果 $MOD$ 不是质数，下面这种写法一般不可靠：

```cpp
inv_a = qpow(a, MOD - 2);
```

除非题目额外保证，或者你已经证明这种写法在当前条件下成立。

---

### 错误二：分母和模数不互质还求逆元

逆元存在的条件是：

$\gcd(a,MOD)=1$

如果：

$\gcd(a,MOD)\ne 1$

那么 $a^{-1}$ 不存在。这时继续求逆元，答案通常就是错的。

---

### 错误三：忘记处理负数

扩展欧几里得求出来的 $x$ 可能是负数。所以最后要写：

```cpp
x %= mod;
if (x < 0) x += mod;
```

这样才能得到范围在 $0$ 到 $mod-1$ 之间的逆元。

---

### 错误四：中间乘法爆 int

如果 $MOD$ 约等于 $10^9$，两个数相乘可能到 $10^{18}$。

所以乘法时要用 `long long`：

```cpp
ans = 1LL * ans * x % MOD;
```

---

## 怎么判断该用哪种方法

如果题目给的是常见质数模数，比如 $998244353$ 或 $1000000007$：

- 单次求逆元，用快速幂
- 预处理组合数，用阶乘逆元
- 预处理 $1$ 到 $n$ 的所有逆元，用线性递推

如果题目给的是合数模数：

- 先检查分母是否和模数互质
- 如果互质，可以用扩展欧几里得
- 如果不互质，不能直接用逆元，要重新分析式子

简单记忆：

- 质数模数：优先快速幂
- 合数模数：优先想 $\gcd$
- 分母不互质：不要硬求逆元

---

## 最后总结

乘法逆元解决的是取模意义下的除法问题。

在模 $MOD$ 意义下，除以 $a$ 等价于乘 $a^{-1}$，前提是 $a^{-1}$ 存在。

也就是：

$\frac{b}{a}\equiv b\times a^{-1}\pmod {MOD}$

而 $a^{-1}$ 存在的条件是：

$\gcd(a,MOD)=1$

比赛中最常用的写法是：

```cpp
long long inv_a = qpow(a, MOD - 2);
```

但这样操作的必要前提是：

- $MOD$ 是质数
- $a$ 不是 $MOD$ 的倍数

只要记住这几个点，逆元就不再是玄学模板，而是一个很自然的工具：

把不能直接做的除法，变成可以安全计算的乘法。

乘法逆元：把取模中的“除法”变成“乘法”

在 OI 里，很多题都会要求答案对一个数取模，比如：

$ans \bmod 998244353$

或者：

$ans \bmod 1000000007$

这时如果式子里有除法，比如：

$\frac{a}{b} \bmod MOD$

我们通常不能直接写：

ans = a / b % MOD;

因为取模之后，普通除法经常会失效。

正确思路是：

不直接除以 $b$
而是乘上 $b$ 在模 $MOD$ 意义下的乘法逆元

也就是把：

$\frac{a}{b}$

改成：

$a \times b^{-1}$

其中 $b^{-1}$ 满足：

$b \times b^{-1} \equiv 1 \pmod {MOD}$

这个 $b^{-1}$ 就叫做 $b$ 在模 $MOD$ 意义下的 乘法逆元。

为什么取模下不能随便除

在普通整数里：

$6 \div 3 = 2$

当然没问题；但在取模的操作里，我们关心的是“余数”。比如模 $5$ 操作有：

$6 \equiv 1 \pmod 5$

如果你先除再取模：

$6 \div 3 = 2$

得到的是 $2$。但如果你先把 $6$ 变成余数：

$6 \equiv 1 \pmod 5$

那问题就变成：

$1 \div 3 \pmod 5$

这时“除以 $3$”到底是什么意思？

在模意义下，我们不把它理解成普通除法，而是理解成：

乘上一个数 $x$，让 $3x$ 的余数等于 $1$。

也就是找：

$3x \equiv 1 \pmod 5$

试一下可以发现：

$3 \times 2 = 6 \equiv 1 \pmod 5$

所以：

$3^{-1} \equiv 2 \pmod 5$

于是：

$1 \div 3 \equiv 1 \times 2 \equiv 2 \pmod 5$

这次结果刚好还是 $2$，但关键是：取模意义下的除法，本质上是乘逆元。

乘法逆元

如果有两个整数 $a$ 和 $x$，满足：

$a \times x \equiv 1 \pmod m$

那么 $x$ 就叫做 $a$ 在模 $m$ 意义下的乘法逆元。

通常写成：

$x \equiv a^{-1} \pmod m$

也就是：

$a \times a^{-1} \equiv 1 \pmod m$

也就是说：

普通数学里，$a$ 的倒数是 $\frac{1}{a}$
取模数学里，$a$ 的“倒数”就是 $a^{-1}$
普通除法里的除以 $a$，在取模里就变成乘 $a^{-1}$

所以：

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

逆元的存在性

逆元不一定存在。我们说 $a$ 在模 $m$ 意义下有逆元，当且仅当：

$\gcd(a,m)=1$

也就是说，$a$ 和 $m$ 必须互质。

比如说 $3$ 和 $5$ 互质，所以 $3$ 在模 $5$ 意义下有逆元；这是因为：

$3 \times 2 \equiv 1 \pmod 5$

所以：

$3^{-1} \equiv 2 \pmod 5$

再举个没有逆元的例子：

$2$ 和 $6$ 不互质，因为：

$\gcd(2,6)=2$

我们想找：

$2x \equiv 1 \pmod 6$

但 $2x$ 一定是偶数，它对 $6$ 取模后只可能是：$0,2,4$，不可能得到 $1$。

所以 $2$ 在模 $6$ 意义下没有逆元。

为什么算法竞赛里经常能用逆元

因为很多题的模数是质数，比如：

$998244353$
$1000000007$
$1000000009$

如果 $MOD$ 是质数，那么只要 $a$ 不是 $MOD$ 的倍数，就一定有：

$\gcd(a,MOD)=1$

也就是说，大多数时候我们要求的分母都有逆元。

于是组合数、概率、期望、DP 计数里的除法，都可以写成乘逆元。

例如：

$\binom{n}{k}=\frac{n!}{k!(n-k)!}$

在模 $MOD$ 意义下可以写成：

$\binom{n}{k}\equiv n! \times (k!)^{-1} \times ((n-k)!)^{-1} \pmod {MOD}$

这就是组合数预处理里经常出现 fac 和 ifac 的原因。

方法一：快速幂求逆元

这是最常用的方法。

前提：

$MOD$ 是质数
$a$ 不是 $MOD$ 的倍数

根据费马小定理：

$a^{MOD-1}\equiv 1 \pmod {MOD}$

把左边拆开看：

$a^{MOD-1}=a\times a^{MOD-2}$

所以：

$a^{MOD-2}\equiv a^{-1} \pmod {MOD}$

也可以写成：

$a^{-1}\equiv a^{MOD-2} \pmod {MOD}$

也就是说，只要求：

$a^{MOD-2} \bmod MOD$

就能得到 $a$ 的逆元。

快速幂代码如下：

using ll = long long;

ll qpow(ll a, ll b, ll mod) {
    ll res = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

ll inv(ll a, ll mod) {
    return qpow(a, mod - 2, mod);
}

使用例子：

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

const int MOD = 998244353;

int main() {
    long long a = 3;
    long long inv_a = inv(a, MOD);
    cout << inv_a << '\n';
    return 0;
}

复杂度：

$O(\log MOD)$

这种写法简单、稳定，比赛里常用。

方法二：扩展欧几里得求逆元

上面的快速幂求逆元法依赖 $MOD$ 是质数。如果 $MOD$ 不一定是质数，但 $a$ 和 $MOD$ 互质，也可以用扩展欧几里得算法。

因为当：

$\gcd(a,m)=1$

根据裴蜀定理，一定存在整数 $x$ 和 $y$，使得：

$ax+my=1$

两边对 $m$ 取模：

$ax+my\equiv 1 \pmod m$

因为：

$my\equiv 0 \pmod m$

所以：

$ax\equiv 1 \pmod m$

这说明 $x$ 就是 $a$ 在模 $m$ 意义下的逆元。

代码如下：

using ll = long long;

ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll x1, y1;
    ll g = exgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - a / b * y1;
    return g;
}

ll inv(ll a, ll mod) {
    ll x, y;
    ll g = exgcd(a, mod, x, y);
    if (g != 1) return -1; // 不存在逆元
    x %= mod;
    if (x < 0) x += mod;
    return x;
}

复杂度：

$O(\log MOD)$

这个方法的优点是：

模数不要求是质数
只要 $a$ 和 $MOD$ 互质，就能求

方法三：线性递推求一整段逆元

有时我们不是只求一个数的逆元，而是要求：

$1^{-1},2^{-1},3^{-1},\dots,n^{-1}$

如果 $MOD$ 是质数，并且 $1 \le i < MOD$，可以用线性递推：

$inv[1]=1$

$inv[i]=(MOD-\lfloor\frac{MOD}{i}\rfloor)\times inv[MOD\bmod i]\bmod MOD$

代码如下：

const int N = 1000000;
const int MOD = 998244353;

long long inv[N + 5];

void init_inv() {
    inv[1] = 1;
    for (int i = 2; i <= N; ++i) {
        inv[i] = 1LL * (MOD - MOD / i) * inv[MOD % i] % MOD;
    }
}

复杂度：$O(n)$

它适合一次性预处理很多个逆元。

阶乘逆元与组合数

组合数是逆元最常见的应用之一。

我们知道：

$\binom{n}{k}=\frac{n!}{k!(n-k)!}$

在模意义下：

$\binom{n}{k}\equiv fac[n]\times ifac[k]\times ifac[n-k]\pmod {MOD}$

其中：

$fac[i]$ 表示 $i!$
$ifac[i]$ 表示 $(i!)^{-1}$

预处理方式如下：

const int N = 1000000;
const int MOD = 998244353;

long long fac[N + 5], ifac[N + 5];

long long qpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

void init_comb() {
    fac[0] = 1;
    for (int i = 1; i <= N; ++i) {
        fac[i] = fac[i - 1] * i % MOD;
    }

    ifac[N] = qpow(fac[N], MOD - 2);
    for (int i = N; i >= 1; --i) {
        ifac[i - 1] = ifac[i] * i % MOD;
    }
}

long long C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fac[n] * ifac[k] % MOD * ifac[n - k] % MOD;
}

注意这个模板默认 $MOD$ 是质数，并且通常要求预处理范围里的阶乘不要变成 $0$，也就是常见场景下有 $N

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com