算法笔记:乘法逆元

Ginkgo True love prevails.

1.乘法逆元的引入

在模运算中,存在下述性质

需要注意的是,结果可能会出现负数,若只需要正数概念下的模,需对结果使用下述变化

可见该性质对于加法、减法、乘法均成立,但在除法运算中

就算在保证整除的情况下也不一定成立


那么我们该如何解决上述问题,使我们能够在除法运算中也使用模运算的性质呢?
可以注意到,乘法与除法为互逆运算,便考虑将除法转化为乘法,找到 使得

若 满足上述等式,则 即为 在模 意义下的乘法逆元

2.乘法逆元的性质

现有下述等式成立

两等式两边同乘 得

整理得

因此,我们只要找到满足 的
就可以得到 在模 意义下的乘法逆元


那么 一定存在吗?

当 的时,上述公式为 ,易得 无实数解,所以 不一定存在

由 可得

设 为 , 的最大公约数,即 ,设 、 的某个因数为 、

因为我们是在整数范围内讨论的逆元概念,所以我们可以推出

或

而且,上述步骤均可逆,因此乘法逆元存在当且仅当 与 互质

3.乘法逆元的求解

(1) 利用费马小定理求解
由费马小定理得,当 为质数时

取 即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
using LL = long long;
LL qpow(LL a, LL b, LL p) {
LL res = 1;
while (b) {
if (b & 1)
res = (res * a) % p;
a = (a * a) % p;
b >>= 1;
}
return res;
}

LL getInv(LL x, LL p) {
return qpow(x, p - 2, p);
}

(2) 利用扩展欧几里得算法求解

扩展欧几里得算法可以得出 的一组

==

由于 与 互质,所以 ,且设 得

=

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
using LL = long long;
LL exgcd(LL a, LL b, LL& x, LL& y) {
if (!b) {
x = 1, y = 0;
return a;
}
LL d = exgcd(b, a % b, y, x), t = x;
x = y;
y = t - (a / b) * y;
return d;
}

LL getInv(LL a, LL p) {
LL x = 1, y = 0;
exgcd(a, p, x, y);
return (x % p + p) % p; // 防止出现负数
}

4.乘法逆元的扩展——线性求逆元

如何求出 依次在模 意义下的逆元?
保证 为质数,且

对于 ,由于 ,设 ,,
在模 的意义下

由上述推导出的递推式得,若 的值已知,则 的值可求。
由于 ,因此我们在依次求 的逆元时, 一定比 先被求出,即在求 时已知

注意到,若按等式处理,所得 的值为负数,需进行下述处理

1
2
3
4
5
6
7
const int maxn = 1e5 + 5;
int inv[maxn];
inv[1] = 1;
for (int i = 2; i <= n; ++i) {
inv[i] = -(p / i) * inv[p % i]; // x_inv = -k * r_inv
inv[i] = (inv[i] % p + p) % p; // x_inv = (x_inv % p + p) %p
}
  • Title: 算法笔记:乘法逆元
  • Author: Ginkgo
  • Created at : 2024-04-21 16:11:24
  • Updated at : 2026-04-26 21:33:17
  • Link: https://g1nkgo7.github.io/2024/04/21/算法笔记-逆元/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments