乘法逆元
残阳如血
·
2024-07-21 16:58:52
·
算法·理论
逆元定义
如果 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\nmid 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)。
扩展欧几里得算法
由[裴蜀定理](https://www.cnblogs.com/oier-wst/p/-/Peishu-theorem)可知，若 $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. 乘法逆元](https://loj.ac/p/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](https://loj.ac/p/161)。
---
显然，对于每一个数用 快速幂 / $\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$ 逆元的复杂度。