乘法逆元学习笔记

lylcpp

·

2025-01-08 21:52:18

·

算法·理论

前言

在讲中国剩余定理的时候，没有系统性的讲一遍乘法逆元，所以有了这一期专栏。

定义

如果有一个线性同余方程 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

假设有一组解

x = x_0 \\

y = y_0 \\

\end{cases}

使得原方程组成立。

又因为 a \bmod b = a - \left \lfloor \frac{a}{b} \right \rfloor b

所以左边等于

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)

所以

x_0 = y_0 \\

y_0 = x_0-\left \lfloor \frac{a}{b} \right \rfloor y_0 \\

\end{cases}

这就是推导过程，在 C++ 中，我们可以采用递归的思想进行求解。

```cpp

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

所以就有递推式：

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 避免出现负数

}

结束语

到这里就结束啦！