乘法逆元
wangchai2009
·
·
算法·理论
乘法逆元
前置知识
二元线性丢番图方程
形如 ax + by = c 的方程称为二元线性丢番图方程，其中 a, b, c \in \Z 且均为常数.
裴蜀定理
对于一个二元线性丢番图方程 ax + by = c，其存在整数解的充要条件是 (a, b) \mid c.
如果存在一组整数解 (x_0, y_0)，则所有解可以表示为 x = x_0 + \dfrac{b}{(a, b)} \cdot k, y = y_0 - \dfrac{a}{(a, b)} \cdot k，其中 k \in \Z.
同余与同余式
### 一元线性同余方程
形如 $ax \equiv b \pmod m$ 的方程，其中 $a, b, m \in \Z$ 且均为常数.
### 欧几里得算法（辗转相除法）
$\forall a, b \in \N_+$，有 $(a,b) = (b, a \bmod b)$.
## 扩展欧几里得算法
### 求二元线性丢番图方程的整数解
对于一个二元线性丢番图方程 $ax + by = c$， 当且仅当 $(a, b) \mid c$ 时， 方程有整数解.
故可以先求
$$ax + by = (a, b)$$
的解，再在等式两边乘以 $\dfrac {c}{(a, b)}$，即可得到原方程的解.
由辗转相除法
$$(b, a \bmod b) = (a, b)$$
可以列出另一个二元线性丢番图方程
$$bx_1 + (a \bmod b)y_1 = (b, a \bmod b)$$
整理
$$
\begin{cases}
(b, a \bmod b) = (a, b)\\
ax + by = (a, b)\\
bx_1 + (a \bmod b)y_1 = (b, a \bmod b)\\
\end{cases}
$$
对于欧几里得算法的流程而言，求解 $(b, a \bmod b)$ 是 求解 $(a, b)$ 的一个子问题，在欧几里得算法回溯时我们需要根据 $bx_1 + (a \bmod b)y_1 = (b, a \bmod b)$ 的解来推导 $ax + by = (a, b)$ 的解.
因为
$$(b, a \bmod b) = (a, b)$$
所以
$$bx_1 + (a \bmod b)y_1 = ax + by$$
又有
$$a \bmod b = a - \lfloor \dfrac{a}{b} \rfloor \cdot b$$
将其带入等式中可得
$$bx_1 + \left(a - \lfloor \dfrac{a}{b} \rfloor \cdot b \right)y_1 = ax + by$$
整理等式
$$ay_1 + bx_1 - \lfloor \dfrac{a}{b} \rfloor \cdot by_1 = ax + by$$
$$ay_1 + b\left(x_1 - \lfloor \dfrac{a}{b} \rfloor y_1\right) = ax + by$$
将等式左右两项分别对应可得
$$x = y_1, y = x_1 - \lfloor \dfrac{a}{b} \rfloor y_1$$
在欧几里得算法的最终状态可以得到 $a = (a, b), b = 0$，此时方程 $ax + by = (a, b)$ 的解显然是 $x = 1, y = 0$. 由于欧几里得算法是递归算法，故可以通过 $x = 1, y = 0$ 以及刚才得出的结论逆推.
此时所求为 $ax + by = (a, b)$ 的一组解，在等式两边同时乘以 $\dfrac {c}{(a, b)}$，就可以求得 $ax + by = c$ 的解.
显然这只是方程的一组解。若记为 $x_0, y_0$，则方程的通解为 $x = x_0 + \dfrac{b}{(a, b)} \cdot k, y = y_0 - \dfrac{a}{(a, b)} \cdot k, k \in \Z$.
```cpp
int Exgcd(int a, int b, int &x, int &y)
{
if (b == 0)
{
x = 1; y = 0;
return a;
}
int ans = Exgcd(b, a % b, x, y);
int tmp = x;
x = y;
y = tmp - a / b * y;
return ans;
}
```
### 求一元线性同余方程的解
由同余的定义，对于一个一元线性同余方程 $ax \equiv b \pmod m$，一定有 $m \mid (ax - b)$.
我们假设 $(ax - b)$ 是 $m$ 的 $-y$ 倍，那么
$$ax - b = -my$$
$$ax + my = b$$
这其实就是一个二元线性丢番图方程. 所以求解一个一元线性同余方程等价于求解一个二元线性丢番图方程.
### 利用扩展欧几里得算法求乘法逆元
在进行模运算时，有时需要对分数取模，但是 $\dfrac{b}{a} \bmod m \ne \dfrac{b \bmod m}{a \bmod m}$，这时就需要一个 $x$ 来代替 $\dfrac{1}{a}$，使得
$$\dfrac{b}{a} \equiv bx \pmod m$$
那么
$$x \equiv \dfrac{1}{a} \pmod m$$
即
$$ax \equiv 1 \pmod m$$
此时将 $x$ 称为 $a$ 模 $m$ 时的乘法逆元，记作 $a^{-1} \pmod m$ 或者 $\text{inv}(a)$.
根据裴蜀定理，当且仅当 $(a, m) \mid 1$ 时， $ax \equiv 1 \pmod m$ 有整数解，即 $a$ 存在乘法逆元的充要条件是 $a$ 与 $m$ 互质.
回顾线性同余方程的标准形式
$$ax \equiv b \pmod m$$
那么 $a$ 的乘法逆元就是 $b = 1$ 时方程的解，用扩展欧几里得算法求解即可.
## 费马小定理求解
若有 $a, m \in \Z$，$m \nmid a$ 且 $m$ 为质数，则有 $a^{m - 1} \equiv 1 \pmod m$.
将式子变形 $a \cdot a ^ {m - 2} \equiv 1 \pmod m$.
根据乘法逆元的定义可以得到 $a$ 在模 $m$ 意义下的乘法逆元为 $a ^ {m - 2}$，用快速幂求解即可.
## 线性递推求解
线性递推解法可以在 $\mathcal{O}(m)$ 时间复杂度内求解区间 $[1, n]$ 内所有数关于 $m$ 的乘法逆元 $(n < m)$.
根据定义易得 $\text{inv}(1) = 1$.
$\forall i \in [1, n] 且 i \in \Z$，设 $m = ki + r$，其中 $k, r \in \Z$，有
$$ki + r \equiv 0 \pmod m$$
两边同时乘以 $i^{-1}r^{-1} \pmod m$，得
$$kr^{-1} + i^{-1} \equiv 0 \pmod m$$
移项，得
$$i^{-1} \equiv -kr^{-1} \pmod m$$
又有
$$k = \lfloor \dfrac{m}{i} \rfloor$$
代入得
$$i^{-1} \equiv -\lfloor \dfrac{m}{i} \rfloor r^{-1} \pmod m$$
又有
$$r = m \bmod i$$
可知
$$r < i$$
故 $\text{inv}(r)$ 一定在求解 $\text{inv}(i)$ 之前就已经推导出.那么
$$\text{inv}(i) \equiv -\lfloor \dfrac{m}{i} \rfloor \cdot \text{inv}(m \bmod i) \pmod m$$
为了防止出现负数，可在等式右边加上 $m$，因为 $m \bmod m = 0$，故不会对答案产生影响.
$$\text{inv}(i) = \left( m -\lfloor \dfrac{m}{i} \rfloor \right) \cdot \text{inv}(m \bmod i) \bmod m$$