概念

对于整数 a 和正整数 m，若存在另一个整数 b 满足 ab \equiv 1 \pmod m，则称 b 是 a 的乘法逆元。

当 a 与模数 m 互质时，可以证明乘法逆元在模 m 意义下存在且唯一，此时可以记 a 的乘法逆元为 a^{-1}。特别地，当模数 m 是一个质数时，所有不被 m 整除的整数都有逆元。

逆元的性质

除法也可以提前取模，即：

\left( \frac{a}{b} \right) \bmod p = (a \bmod p) \cdot (b \bmod p)^{-1} \bmod p.

单个数的逆元

Fermat 小定理

利用 Fermat 小定理可以求出模数是质数时的乘法逆元。

当 p 是一个质数，且 a \bmod p \ne 0 时，有 a^{p - 1} \equiv 1 \pmod{p}，于是有 a \cdot a^{p - 2} \equiv 1 \pmod p。由定义，a 在模 p 意义下的乘法逆元就是 a^{p - 2}。

配合快速幂就可以在 O(\log p) 的时间内求出乘法逆元。

Euler 定理

当 m, n 互质时，有

n^{\varphi(m)} \equiv 1 \pmod{m}.

于是，模 m 意义下 n 的乘法逆元为

n^{-1} \equiv n ^{\varphi(m) - 1} \pmod{m}.

Fermat 小定理是 Euler 定理的一种特殊情况。

扩展 Euclid 算法

扩展 Euclid 算法（exGCD）同样可以求出乘法逆元。

根据定义，a 在模 m 意义下的乘法逆元 b 指的是

ab \equiv 1 \pmod{m}.

如果不用同余的写法，就是

ba + km = 1.

因此，当 a, m 互质时，上式代求的 b 就成为了 Bezout 定理的系数，可以用 exGCD 算法得到。

多个数的逆元

线性求逆元

用递推的方法，在 O(n) 的时间内求出 [1, n] 中所有数的逆元。

首先，显然有 1^{-1} \equiv 1。然后，要求 a \ge 2 的逆元，先写出 p 除以 a 的带余除法：p = q a + r，模 p 得到 qa + r \equiv 0，移项得到：

a^{-1} \equiv -q r^{-1} \equiv - \left \lfloor \frac{p}{a} \right \rfloor \left( p \bmod a \right)^{-1} \pmod{p}.

而小于 a 的数的逆元已经在 a 之前求出，故上式可以递推。

constexpr ull P = 1e9 + 7, MAXN = 1e5;
ull inv[MAXN + 5];

void pre_inv()
{
    inv[1] = 1;
    for (size_t i = 2; i <= MAXN; i++)
    {
        inv[i] = (P - P / i) * inv[P % i] % P;
    }
}

线性求阶乘逆元

用逆推的方法，可以线性求出 1!, 2!, \dots, n! 的逆元。

首先使用 Fermat 小定理（或其他方法）求出 n! 的逆元，然后由 n! = n (n - 1)! 可得：

[(n - 1)!]^{-1} \equiv n \cdot (n!)^{-1} \pmod{p}.

逐项逆推就可以得到 (n - 1)!, (n - 2)!, \dots, 1! 的逆元。时间复杂度 O(n + \log p)。

事实上，该方法可以求任意前缀积的逆元，只要保证前缀积在模数意义下可逆。

void preprocess()
{
    constexpr ull n = 2e5;
    f[0] = 1;
    for (ull i = 1; i <= n; i++)
    {
        f[i] = f[i - 1] * i % P;
    }
    f_inv[n] = pow(f[n], P - 2);
    for (ull i = n; i >= 1; i--)
    {
        f_inv[i - 1] = i * f_inv[i] % P;
    }
}

概念