乘法逆元

在模意义下，我们有 $a \bmod c + b \bmod c = (a + b) \bmod c$，$a \bmod c - b \bmod c = (a - b) \bmod c$，$(a \bmod c) \times (b \bmod c) = ab \bmod c$，但是没有 $\dfrac{a \bmod c}{b \bmod c} = \dfrac{a}{b} \bmod c$。

那，在模意义下遇到除法该怎么办呢？

我们有乘法逆元。

定义 $a$ 模 $p$ 意义下的乘法逆元为 $a^{-1}$，$a \times a^{-1} \equiv 1 \pmod p$。

当 $\gcd(a, p) = 1$ 时，乘法逆元才存在。否则设 $b \in [0, p)$，$\gcd(a \times b, p) > 1$ 也成立，要么 $p | a \times b$，要么 $a \times b \bmod p > 1$。

由于质数与比它小的数都互质，所以模质数 $p$ 意义下所有非零元都有乘法逆元，这就成了一个域。

乘法逆元的求法

拓展欧几里得算法

根据逆元的定义，设 $x$ 为 $a$ 的逆元，$ax \equiv 1 \pmod m$，那么 $ax - by = 1$，可以直接用拓欧求解，时间复杂度为 $O(\log a)$，一般情况下跑不满。

费马小定理

费马小定理 $a^p \equiv a \pmod p$，其中 $p$ 为任意质数而 $a$ 为与其互质的任意整数。

证明在这里。

根据费马小定理，$a^{p - 1} \equiv 1 \pmod p$，$a^{p - 2} \times p \equiv 1 \pmod p$，所以 $a^{p - 2}$ 就是 $a$ 的逆元。

用快速幂单次求时间复杂度可以达到 $O(\log p)$，比拓欧慢，但是写起来简单。

$O(n)$ 预处理 $1 \sim n$ 的逆元

神奇的思路。假设 $1 \sim i - 1$ 的逆元已求出，现在要求 $i$ 的逆元。

模数 $p$ 可以表示为 $ki + r$，那么 $ki + r \equiv 0 \pmod p$。

两边同时乘以 $i^{-1}r^{-1}$ 得 $kr^{-1} + i^{-1} \equiv 0 \pmod p$，$i^{-1} \equiv -kr^{-1} \pmod p$。

$r^{-1}$ 是已经求出的，于是就可以线性求逆元了。

$O(n)$ 预处理 $1!, 2!, \dots, n!$ 的逆元

显然 $(n!)^{-1} = \prod_{i = 1}^n i^{-1}$，求完 $1 \sim n$ 的逆元后再跑一遍前缀积即可。