逆元定义
如果 $ax\equiv 1\pmod p$，则称 $x$ 为 $a$ 在模 $p$ 意义下的乘法逆元。
逆元存在当且仅当 $a\perp p$，即 $\gcd(a,p)=1$。
将 $ax\equiv 1\pmod p$ 转化可得 $x\equiv\dfrac{1}{a}\pmod p$，那么模意义下 $t \div a$ 就相当于 $t \times x$。
快速求单个数的逆元
快速幂
费马小定理
当 $p\not\mid a$ 且 $p\in\mathbb{P}$ 时，有
$$ a^{p-1}\equiv 1\pmod p $$
由此转化可得 $a\times a^{p-2}\equiv 1\pmod p$，此时就可以发现 $a^{p-2}$ 即为 $a$ 在模 $p$ 意义下的乘法逆元。
此时可以用快速幂计算逆元，时间复杂度 $O(\log p)$。
扩展欧几里得算法
$\text{Exgcd}$ 也可以用于求逆元。
由裴蜀定理可知，若 $a\perp p$，则必然 $\exist\, y$，使得 $a\times x+p\times y=1$ 成立。
容易发现，$a\times x+p\times y=1\Leftrightarrow a\times x\equiv 1\pmod p$。
使用 $\text{exgcd}$ 解出这个方程即可，时间复杂度 $O(\log p)$。
线性求 $1\sim n$ 的逆元
例题：loj #110. 乘法逆元。
现要求在 $O(n)$ 的时间内，求出模 $m$ 的意义下，$[1,m)$ 中所有数的乘法逆元。
容易发现，$\forall\, m\in\mathbb{Z}$，有 $1 \times 1 \equiv 1\pmod m$，所以 $1$ 的逆元恒为 $1$。
考虑 递推。
假设我们已知 $[1,x)$ 内所有数的逆元，需要求出 $x$ 的逆元。
将模数 $m$ 表示为 $kx+t$，其中 $k=\Big\lfloor\dfrac{m}{x}\Big\rfloor$，$t=m\bmod x$。
由此可得 $kx+t\equiv 0\pmod m$。
两边同乘 $x^{-1}\times t^{-1}\pmod m$，可得
$$
\begin{aligned}
kx\times x^{-1}\times t^{-1}+t\times x^{-1}\times t^{-1}\equiv 0\pmod m\
k\times t^{-1}+x^{-1}\equiv 0\pmod m\
\end{aligned}
$$
即可得 $x^{-1}\equiv k\times t^{-1}\pmod m$。
在此基础上代入 $k=\Big\lfloor\dfrac{m}{x}\Big\rfloor$，$t=m\bmod x$，可得
$$
x^{-1} \equiv -\Big\lfloor\dfrac{m}{x}\Big\rfloor(m\bmod x)^{-1}\pmod m
$$
由于 $(m\bmod x)^{-1}\in[1,x)$，所以 $(m\bmod x)^{-1}$ 已知，线性递推即可。
- $\textbf{PS 1}$：当 $m\bmod x=0$ 时 $x$ 不存在模 $m$ 意义下的乘法逆元。
- $\textbf{PS 2}$：由于 $\text{C++}$ 中负数取模的结果为负数，所以在实际实现时递推式应写为
(m - m / x) * inv[m % x] % m。
综上所述，递推式即为：
$$
x^{-1}=
\begin{cases}
1&x=1\\
-\Big\lfloor\dfrac{m}{x}\Big\rfloor(m\bmod x)^{-1}&x\not=1
\end{cases}
\pmod m
$$
线性递推即可在 $O(n)$ 的时间内完成。
线性求任意 $n$ 个数的逆元
例题：loj #161 乘法逆元 2。
显然，对于每一个数用 快速幂 / $\text{exgcd}$ 求解，时间复杂度为 $O(n\log p)$，无法通过本题。
考虑使用前缀积 $\{s_n\}$，其中 $s_i$ 记录 $\prod_{j=1}^{i}a_j$。
此外需要前缀积的逆元，使用 $\{t_n\}$ 序列，其中 $t_i=s_{i}^{-1}\pmod p$。
接下来可以通过 快速幂 / $\text{exgcd}$ 求解 $s_n$ 的逆元，记为 $t_n$。
接下来可以通过如下公式线性递推求出 $\{t_n\}$：
$$
t_i \equiv s_i^{-1} \equiv \dfrac{1}{\prod_{j=1}^{i}a_j} \equiv \dfrac{a_{i+1}}{\prod_{j=1}^{i+1}{a_j}} \equiv a_{i+1}\times s_{i+1}^{-1} \equiv a_{i+1}\times t_{i+1}\pmod p
$$
记原序列的逆元为 $\{\text{inv}_n\}$，其中 $\text{inv}_i=a_{i}^{-1}\pmod p$。
由于已知前缀积数组的逆元，那么
$$
\text{inv}_i \equiv a_{i}^{-1} \equiv \dfrac{1}{a_i} \equiv \dfrac{1}{\dfrac{s_i}{s_{i-1}}} \equiv \dfrac{s_{i-1}}{s_i} \equiv s_{i-1}\times t_{i}
$$
故递推即可，时间复杂度为 $O(n+\log p)$，其中 $O(\log p)$ 是求 $s_n$ 逆元的复杂度。