前言
在讲中国剩余定理的时候，没有系统性的讲一遍乘法逆元，所以有了这一期专栏。
定义
如果有一个线性同余方程 \(ax\equiv1\pmod{p}\)，则称 \(x\) 为 \(a\equiv p\) 的乘法逆元。记作 \(a^{-1}\)。
但是，只有当 \(\gcd(a,p)=1\) 时，乘法逆元才存在。
求乘法逆元
费马小定理
如果 \(\gcd(a,p)=1\)，那么 \(a^{p-1}\equiv1\pmod{p}\)。
经过计算，得：\(a\times a^{p-2} \equiv 1 \pmod p\)。
所以，在 \(\gcd(a,p)=1\) 时，\(a^{p-2}\) 就是 \(a\) 的乘法逆元。
这个情况在 C++ 可以用快速幂进行求解。
扩展欧几里得（exgcd）
exgcd 用来求 \(ax+by = \gcd(a,b)\) 的解。
在求解过程中我们需要分类讨论。
当 \(b=0\) 时，化简得 \(ax = \gcd(a,0)\)，因为 \(\gcd(a,0)=a\)，所以 \(ax = a\)，解得 \(x=1\)。
此时，\(y\) 有无数组解，我们不妨设 \(y=0\)。
当 \(b \ne 0\) 时，\(\gcd(a,b) = \gcd(b, a \bmod b)\)（欧几里得算法）
于是 \(ax+by=\gcd(b, a \bmod b)\)
此时可以看做 \(a\) 对应 \(b\)，\(b\) 对应 \(a \bmod b\)，不是相等！
所以左边等于 \(bx+(a \bmod b) y\)
假设有一组解
\(\begin{cases} x = x_0 \\ y = y_0 \\ \end{cases}\)
使得原方程组成立。
又因为 \(a \bmod b = a - \left \lfloor \frac{a}{b} \right \rfloor b\)
所以左边等于
\(\begin{aligned} bx_0+(a - \left \lfloor \frac{a}{b} \right \rfloor b)y_0 \\ =bx_0+ay_0-\left \lfloor \frac{a}{b} \right \rfloor by_0 \\ =ay_0+b(x_0-\left \lfloor \frac{a}{b} \right \rfloor y_0) \end{aligned}\)
所以 \(ax_0+by_0 = ay_0+b(x_0-\left \lfloor \frac{a}{b} \right \rfloor y_0)\)
所以
\(\begin{cases} x_0 = y_0 \\ y_0 = x_0-\left \lfloor \frac{a}{b} \right \rfloor y_0 \\ \end{cases}\)
这就是推导过程，在 C++ 中，我们可以采用递归的思想进行求解。
\(x\) 就是我们要求的乘法逆元，而 \(ax \equiv 1 \pmod p\)，可以看做 \(ax \bmod p = 1\)，令 \(p = by\)，则 \(ax + by = \gcd(a,p)\)，又因为乘法逆元存在的条件为 \(\gcd(a,p)=1\)，所以 \(ax+by=1\)。此时，用 exgcd 求 \(x\)。
void exgcd(ll a, ll b, ll &x, ll &y) {
if (!b) { // b=0 的情况
x = 1, y = 0;
return ;
}
exgcd(b, a % b, y, x); // 注意这里 y 和 x 交换一下
y = y - (a / b) * y; // 这里的第二个 y 可以看做 x
}
注意，\(x\) 可能最终是负数，所以算出来最后要先模 \(p\)，再加 \(p\)，再模 \(p\)。
即x = (x % p + p) % p;
递推法求乘法逆元
这一点非常的重要！
应用：求 \(1 \sim n\) 的所有乘法逆元。
时间复杂度：\(O(n)\)。
首先，我们要知道 \(1^{-1} \equiv 1 \pmod p\)，因为：显然，在 \(p\) 下，\(1\) 是 \(1\) 的乘法逆元。
其次，对于递归情况 \(i^{-1}\)，我们设 \(k=\left \lfloor \frac{p}{i} \right \rfloor, j = p \bmod i\)，则有 \(p = ki + j\)。
所以，在模 \(p\) 意义下，\(ki+j \equiv 0 \pmod p\)。
此时，左右两边同时乘以 \(i^{-1} \times j^{-1}\)，得：
\(ki \times i^{-1} \times j^{-1} + j \times i^{-1} \times j^{-1} \equiv 0 \pmod p\)
\(kj^{-1}+i^{-1} \equiv 0 \pmod p\)
\(i^-1 \equiv -kj^{-1} \pmod p\)
再带入 \(j = p \bmod i, k = \left \lfloor \frac{p}{i} \right \rfloor\)，得：
\(i^{-1} \equiv -\left \lfloor \frac{p}{i} \right \rfloor (p \bmod i)^{-1} \pmod p\)
注意， \(p \bmod i < i\)，又因为在递推的过程中，我们已经求出了所有小于 \(i\) 的在模 \(p\) 意义下的乘法逆元，可表示为 \(q^{-1}, q<i\)。
所以就有递推式：
\(inv[i] \equiv \begin{cases} 1 \,\,\,\,\,\,\,(i=1) \\ -\left \lfloor \frac{p}{i} \right \rfloor inv[p \bmod i] \,\,\,\,\,\,\, (i \ne 1, i > 1)\\ \end{cases} \pmod p\)
这也可以用 C++ 的代码来表示：
for (int i = 1; i <= n; i++) {
if (i == 1) inv[i] = 1;
else inv[i] = (long long)(p - p / i) * inv[p % i] % p;
// p - p / i 避免出现负数
}
结束语
到这里就结束啦！
标签：lfloor,gcd,pmod,bmod,笔记,逆元,乘法 From： https://www.cnblogs.com/panda-lyl/p/18666143