乘法逆元

注意：若无特殊说明，本章涉及的变量皆为正整数.

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

$$a·a^{-1}≡1 \ (\bmod \ p)$$

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

$$\dfrac{a}{b}≡a\cdot b^{-1} \ (\bmod \ p)$$

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

对于整数 $x$，可以求解关于 $x^{-1}$ 的 线性同余方程 $x\cdot x^{-1}≡1 \ (\bmod \ 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{aligned} a^{p-1}&≡1 \ (\bmod \ p)\\ a^{p-2}&≡a^{-1} \ (\bmod \ p) \end{aligned}$$

$∴p^{-1}=a^{p-2} \bmod p$. 其中 $a^{p-2}$ 可用 快速幂 求解.

求 $1\sim n$ 在模 $p$ 意义下的逆元.

假设已经求出了 $1\sim i-1$ 的乘法逆元.

设 $ m=p \bmod i=p-\Big\lfloor\frac{p}{i}\Big\rfloor\cdot i$，则有：

$$m+\Big\lfloor\frac{p}{i}\Big\rfloor\cdot i≡0 \ (\bmod \ p)$$

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

$$i^{-1}+\Big\lfloor\frac{p}{i}\Big\rfloor\cdot m^{-1}≡0 \ (\bmod \ p)$$

由于 $m=p \bmod i≤i-1$，所以 $m^{-1}$ 已知. 于是得到 $i^{-1}$ 的表达式：

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

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; // 化为正整数
}