INFO

若无特殊说明，本章涉及的变量皆为正整数。

定义

若 $a\cdot b\equiv 1(\mathrm{mod}p)$，则 $b$ 为 $a$ 在模 $p$ 意义下的逆元，记作 $a^{-1}$ 或 $\mathrm{inv}(a)$。

$$a·a^{-1}\equiv 1(\mathrm{mod}p)$$

乘法逆元能够很好地将模运算中的除法转为乘法：

$${\displaystyle \frac{a}{b}}\equiv a\cdot b^{-1}(\mathrm{mod}p)$$

在模运算中，$a^{-1}$ 是整数，并不是 $a$ 的 $-1$ 次方。

解法

对于整数 $x$，可以求解关于 $x^{-1}$ 的 线性同余方程 $x\cdot x^{-1}\equiv 1(\mathrm{mod}p)$，其中 $x$ 为已知常数。

int exGcd(int a, int b, int& x, int& y) {
    if(b == 0) { x = 1, y = 0; return a; }
    int d = exGcd(b, a % b, x, y);
    int t = x; x = y, y = t - a / b * y;
    return d;
}

int liEu(int a, int b, int c) { // a·x ≡ c (mod b)
    int x, y, d = exGcd(a, b, x, y);
    x *= (c / d);
    int t = b / d;
    return (x % t + t) % t;
}

int inv(int x, int m) {
    return liEu(x, m, 1);
}

模为质数的逆元

当 $p$ 为质数时，由 费马小定理 得：

$$\begin{array}{rl}{a}^{p-1}& \equiv 1(\mathrm{mod}p)\\ a^{p-2}& \equiv a^{-1}(\mathrm{mod}p)\end{array}$$

$\therefore p^{-1}=\phantom{0}$$\phantom{0}{a}^{p-2}modp$，其中 $a^{p-2}$ 可用 快速幂 求解。

线性求逆元

求 $1\cdots n$ 在模 $p$ 意义下的逆元。

假设已经求出了 $1\cdots i-\phantom{0}$$\phantom{0}1$ 的乘法逆元。

设 $m=\phantom{0}$$\phantom{0}pmodi=\phantom{0}$$\phantom{0}p-\phantom{0}$$\phantom{0}\lfloor {\displaystyle \frac{p}{i}}\rfloor \cdot i$，则有：

$$m+\lfloor \frac{p}{i}\rfloor \cdot i\equiv 0(\mathrm{mod}p)$$

两边同乘 $m^{-1}{i}^{-1}$：

$$i^{-1}+\lfloor \frac{p}{i}\rfloor \cdot m^{-1}\equiv 0(\mathrm{mod}p)$$

由于 $m=\phantom{0}$$\phantom{0}pmodi\le i-\phantom{0}$$\phantom{0}1$，所以 $m^{-1}$ 已知. 于是得到 $i^{-1}$ 的表达式：

$$i^{-1}=(-\lfloor \frac{p}{i}\rfloor \cdot (pmodi{)}^{-1})modp$$

inv[1] = 1; // 1 的乘法逆元 = 1
for (int i = 2; i <= n; i ++) {
    inv[i] = (- p / i * inv[p % i]) % p;
    inv[i] = (inv[i] + p) % p; // 化为正整数
}