乘法逆元
zifuneko
·
·
算法·理论
乘法逆元的定义
乘法逆元是一个数 b，对于一个整数 a，满足以下公式：
a×b \equiv 1\ (\bmod\ m)
即 a 和 b 的乘积对 m 取余后等于 1。只有当 a 和 m 互质（\gcd(a,m)=1），乘法逆元才存在。
费马小定理
适用条件：模数 m 必须是素数，且 a 和 m 互质。
公式推导
费马小定理告诉我们，如果 m 是素数且 a 和 m 互质，则：
a^{m-1} \equiv 1 \ (\bmod\ m)
将两边同时除以 a ，得到：
a^{m-2} \equiv a^{-1} \ (\bmod\ m)
因此，乘法逆元 a^{-1}\ (\bmod \ m) 可以用以下公式计算：
a^{-1} \equiv a^{m-2} \ (\bmod\ m)
例子：求 3 在模 7 下的逆元
模数 m=7，且 m 是质数，使用公式 a^{m-2} \bmod\ m：
3^{-1} \equiv 3^{7-2} \equiv 3^5\ (\bmod\ 7)
直接计算 3^5 \bmod 7 = 5；
逐步计算 3^5 \bmod 7：
-
3^2 = 9 \equiv 2\ (\bmod\ 7)
-
3^4 = (3^2)^2 = 2^2 = 4\ (\bmod\ 7)
-
3^5 = 3^4 \times 3 = 4 \times 3 = 12 \equiv 5\ (\bmod\ 7)
## 扩展欧几里得
**适用条件**：只要 $a$ 和 $m$ 互质即可，无需 $m$ 是素数。
### **基本原理**
扩展欧几里得算法不仅能求最大公约数，还能找到整数 $x$ 和 $y$ 使得：
$$$ax+my=\gcd(a, m)$$$
当 $\gcd(a,m)=1$ 时，方程变为：
$$$ax+my=1$$$
将方程两边对 $m$ 取模，那么 $my$ 对 $m$ 取模即 $0$，得到：
$$$ax \equiv 1\ (\bmod\ m)$$$
这表明 $x$ 就是 $a$ 的乘法逆元。
### 步骤
**1. 普通欧几里得算法：求最大公约数（GCD）**
我们先通过普通的欧几里得算法（辗转相除法）求出两个数的最大公约数。假设我们有两个整数 $a$ 和 $b$，我们通过以下递归步骤来计算它们的 GCD：
1. $a=b \times q_1+r_1
-
b=r_1\times q_2+r_2
-
r_1=r_2\times q_3+r_3
-
······
-
r_{n-2} = r_{n-1} \times q_n + r_n
- 最终直到某一余数为零为止，最后一个非零余数就是 \gcd(1,b)。
2.\ 反向推导：扩展过程
在计算 \gcd(a,m) 的过程中，我们逐步记录每一次除法的余数和商。然后通过反向推导的方式，得到整数 x 和 y，使得：
ax+my=\gcd(a, m)
在 \gcd(a,m) = 1 的情况下，x 就是 a 对模 m 的乘法逆元。
例子：求 3 在模 11 下的逆元
-
用普通欧几里得算法（辗转相处法）求 \gcd(3,11)：
· 11 = 3 \times 3 + 2 （11 \div 3 = 3 \cdots 2）
· 3 = 2 \times 1 + 1（3 \div 2 = 1 \cdots 1）
· 2 = 2 \times 1 + 0（2 \div 1 = 2 \cdots 0）
最后 \gcd(3,11) = 1，表示 3 和 11 互质，所以乘法逆元存在。
-
反向推导（扩展欧几里得算法）：
从第二步（3 = 2 \times 1 + 1）反向推导，计算 x 和 y。
从第二步 3 = 2 \times 1 + 1 得到：
1 = 3 - 2 \times 1
然后，将第一步中的 2 = 111-3\times3 带入上式：
1 = 3 - 1 \times (11 - 3 \times 3)
1 = 3 - 1 \times 11 + 3 \times 3
1 = 4 \times 3 - 1 \times 11
因此得到：
3 \times 4 + 11 \times (-1) = 1
## 乘法逆元的作用
这里列举两个常用的作用。
### 求解模线性同余方程
乘法逆元可以用来求解模线性同余方程：
$$$ax \equiv b \ (\bmod\ m)$$$
当 $a$ 和 $m$ 互质时，方程有唯一解，解法是通过计算 $a$ 在模 $m$ 下的逆元 $a^{-1}
x \equiv b \sdot a^{-1}\ (\bmod\ m)
示例：
求解3x \equiv 7\ (\bmod\ 11)：
- 先求 3 在 \bmod\ 11 下的逆元，3^{-1} \equiv 4\ (\bmod\ m)
- 解方程：x \equiv 7\sdot 4 \equiv 28 \equiv 6\ (\bmod\ 11)。
\therefore x=6
计算分数的模运算
在整数模运算中，分数无法直接处理。例如，计算 \frac{a}{b}\ (\bmod\ m) 时，可以通过乘法逆元将其转化为：
\frac a b \equiv a\sdot b^{-1}\ (\bmod\ m)
## 代码
### 费马小定理 + 快速幂
```cpp
int qpow(int x, int y)
{
int res = 1;
for(; y > 0; x = (x * x) % mod, y >>= 1)
if(y & 1) res = (res * x) % mod;
return res;
}
int inv(int a) {return qpow(a, mod - 2);}
```
### 扩展欧几里得
```cpp
int exgcd(int a, int b, int &x, int &y)
{
if(b == 0) {x = 1; y = 0; return a;}
int d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
int inv(int a)
{
int x, y;
exgcd(a, mod, x, y);
return (x + mod) % mod;
}
```
### 线性求 $\bold{1-n}$ 逆元
```cpp
void init(int m)
{
inv[1] = 1;
for(int i = 2; i <= m; ++i) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
}
```
### 线性求 $\bold{1-n}$ 逆元（妙招）
```cpp
void init(int m)
{
fac[0] = 1;
for(int i = 1; i <= m; ++i) fac[i] = (fac[i - 1] * i) % mod;
fac_inv[m] = qpow(fac[m], mod - 2);
for(int i = m; i >= 1; --i) fac_inv[i - 1] = (fac_inv[i] * i) % mod;
for(int i = 1; i <= m; ++i) inv[i] = (fac_inv[i] * fac[i - 1]) % mod;
}
```
### 线性求 $\bold{\text{val}_1,\text{val}_2,...,\text{val}_n}$ 逆元
```cpp
void init(int m)
{
fac[0] = 1;
for(int i = 1; i <= m; ++i) fac[i] = (fac[i - 1] * val[i]) % mod;
fac_inv[m] = qpow(fac[m], mod - 2);
for(int i = m; i >= 1; --i) fac_inv[i - 1] = (fac_inv[i] * val[i]) % mod;
for(int i = 1; i <= m; ++i) inv[i] = (fac_inv[i] * fac[i - 1]) % mod;
}
```
## 总结
- 费马小定理：适合模数 $m$ 是素数时使用，直接计算 $a^{m-2} \bmod m$。
- 扩展欧几里得算法：通用方法，无论模数是否是素数，只要 $a$ 和 $m$ 互质，都可以用。
- OI Wiki: https://oi-wiki.org/math/number-theory/inverse/