【乘法逆元】看这一篇就够了！乘法逆元的证明、详解及应用。
yanxiashi
·
·
个人记录
本文章为乘法逆元详解。
前一到二节属于前置知识：同余。
乘法逆元的讲解从第三节开始。
一、同余运算
-
(a+b)\bmod m=[(a\bmod m)+(b\bmod m)]\bmod m
-
(a-b)\bmod m=[(a\bmod m)-(b\bmod m) + m]\bmod m
-
(a\times b) \bmod m = [(a \bmod m) \times (b \bmod m)] \bmod m
-
(a\div b) \bmod m ≠ [(a \bmod m) \div (b \bmod m)] \bmod m
如：(12\div3) \bmod 6 = 4 ≠ (12 \bmod 6) \div (3 \bmod 6)
二、同余性质
-
若 a \equiv b\pmod m，则 m|(a-b)。
-
同加性，若 a\equiv b\pmod m，则 a+c \equiv b+c \pmod m 。
-
同乘性，若 a \equiv b \pmod m，则 ac \equiv bc \pmod m 。
逆性质：若 ac \equiv bc \pmod m ，且 \gcd(c,m)=1，有 a \equiv b \pmod m。
证明：ac-pm=bc-qm ，(a-b)c=(p-q)m，c 与 m 互质，证明 a-b 为 m 的倍数，则 a \equiv b \pmod m。
-
同幂性：若 a\equiv b\pmod m，则 a^c\equiv b^c\pmod m。
三、乘法逆元
对于任意整数 a 而言，如果 a 和 p 互质，存在一个整数 x 使得 a\times x \equiv 1\pmod p ，则有：
\begin{aligned} b\div a\bmod p&=b\div a\times(a\times x)\bmod p \\&=b\div (a\times a)\times x\bmod p\\&=b\times x\bmod p \end{aligned}
我们可以借此解决运算法则四遇到的问题。
例如： $2\times 5 \equiv 1\pmod 9$，则 $5$ 是 $2$ 关于模 $9$ 的乘法逆元。所以 $8\div2\bmod9=8\times5\bmod9=4$。
有了乘法逆元之后，$b\div a\bmod p$，如果 $a，p$ 互质，那么就有：
$$
b\div a\bmod p=(b\bmod p\times a^{-1}\bmod p)\bmod p
$$
# 四、如何求乘法逆元
### 1.费马小定理
费马小定理：若 $p$ 是质数，对任意整数 $a$ 不是 $p$ 的倍数，有 $a^{p-1}\equiv 1\pmod p$，也可以写作 $a^{p}\equiv a\pmod p$。
证明：根据同余的性质，$a,2a,3a……,(p-1)a$ 分别 $\bmod p$ 的结果各不相同。那么：
$$
\begin{aligned}a\times2a\times3a……\times(p-1)a&\equiv 1\times2\times 3……\times(p-1)\pmod p\\a^{p-1}\times[1\times2\times 3……\times(p-1)]&\equiv1\times2\times 3……\times(p-1)\pmod p\\a^{p-1}&\equiv 1\pmod p\end{aligned}
$$
如何求乘法逆元： 若 $p$ 是质数，则有 $a^{p-1}\equiv 1\pmod p$，而 $a\times x\equiv 1\pmod p$，所以 $a^{p-2}$ 是 $a$ 模 $p$ 意义下的的乘法逆元。
可以用快速幂，时间复杂度为 $O(\log p)$。
***
### 2.快速求阶乘逆元
$$
\begin{aligned} a\over{(n-1)!}&{\equiv} {{a}\over{n!}}\times n{\pmod p}\\ [(n-1)!]^{-1}&\equiv (n!)^{-1}\times n\pmod p\end{aligned}
$$
$inv[n]$ 表示 $n$ 的阶乘在模 $p$ 意义下的的乘法逆元 $(n<p)$，显然 $inv[n-1]\equiv inv[n]\times n$。
可以先用费马小定理先求出 $inv[n]$，接着推出所有逆元。
***
### 3.快速求连续自然数逆元
假设已知 $i=1$ 的逆是 $1$。递推求 $i>1$ 时的逆。
1. 设$k$ 是 $p\div i$ 的商，$r$ 是 $p\div i$ 的余数，则 $k\times i+r\equiv 0\pmod p$；
2. 在等式两边同乘 $i^{-1}\times r^{-1}$，得到 $k\times r^{-1}+i^{-1}\equiv 0\pmod p$；
3. 移项得到 $i^{-1}\equiv -k\times r^{-1}\pmod p$，即 $i^{-1}\equiv -\lfloor{{p}\over{i}} \rfloor\times r^{-1}\pmod p$；
4. 最后右边加上 $p$ ，得到 $i^{-1}\equiv p-\lfloor{{p}\over{i}} \rfloor\times r^{-1}\pmod p$。
下面是洛谷 [P3811 乘法逆元](https://www.luogu.com.cn/problem/P3811) 的部分代码：
```cpp
long long inv[maxn];
void inverse(long long n, long long p){
inv[1] = 1;
for(int i = 2; i <= n; ++i)
inv[i] = (p - p/i) * inv[p % i] % p;
}
```
***
### 4.非连续数字快速求逆元
设有 $n$ 个非连续数字，快速求逆元。
仍然使用快速幂，复杂度为 $O(n\log n)$，并非最优。
设：
1. 非连续数字为 $a_1，a_2，a_3……a_n$；
2. $s[i]=a_1\times a_2\times ……\times a_i$；
3. $e[i]=a_n\times a_{n-1}\times……\times a_i$；
4. $INV=(a_1\times a_2\times ……\times a_n)$的逆元。
则 $inv[i]=INV\times s[i-1]\times e[i+1]$。
这样可以 $O(n)$ 得到所有数的逆元。
# 五.结束