在数论中如果 a b ≡ 1 m o d p abequiv 1 mod p ab≡1 mod p，我们称a、b在模p的情况下互为乘法逆元。
在取模运算中加减法和乘法都是封闭的
即
(a + b) % p = a % p + b % p
(a - b) % p = a % p - b % p
a
×
times
× b % p = a % p
×
times
× b % p
但是遇到除法就麻烦了，除法运算对取模运算不封闭，且运算过程中会产生小数，于是就引入了逆元这个概念，a、b在模p情况下互为乘法逆元，说明在模p意义下b和 1 a frac{1}{a} a1的意义相同，这样就解决了小数和除法取模的问题
计算逆元的三种方法：扩展欧几里得算法、费马小定理、线性递推
扩展欧几里得
假设
a
b
≡
1
(
m
o
d
m
)
abequiv 1(mod m)
ab≡1(mod m)
这个方程可以转化为
a
x
+
m
y
=
1
ax + my = 1
ax+my=1用扩展欧几里德算法求出x和y即可计算出b，
b
=
(
x
%
m
+
m
)
%
m
b = (x % m + m) % m
b=(x % m + m) % m这是为了把b变成正数
1
2
3
4
5
6
7
8
9
10int exgcd(int a, int b, int &x, int &y){ if(!b){ x = 1, y = 0; return a; } int d = exgcd(b, a % b, y, x); y -= a / b * x; return d; }
费马小定理
若 m m m是质数，且 g c d ( a , m ) = 1 gcd(a, m) = 1 gcd(a,m)=1，则有 a m − 1 ≡ 1 ( m o d m ) a^{m - 1}equiv 1 (mod m) am−1≡1 (mod m)
所以逆元为 a m − 2 a^{m - 2} am−2，使用快速幂计算即可
1
2
3
4
5
6
7
8
9
10
11//快速幂 int qmi(int a, int b, int p){ int res = 1; while(b){ if(b & 1) res = (LL)res * a % p; b >>= 1; a = (LL)a * a % p; } return res; }
线性递推
P3811 【模板】乘法逆元
设 m = i × k + r ， ( 1 < r < i < m ) m = itimes k + r，(1<r<i<m) m=i×k+r，(1<r<i<m)，即 k = ⌊ m / i ⌋ , r = m m o d i k=left lfloor m/i right rfloor,r=m mod i k=⌊m/i⌋,r=m mod i
放在 ( m o d m ) (mod m) (mod m)的意义下可得到
i × k + r ≡ 0 ( m o d m ) itimes k+requiv 0(mod m) i×k+r≡0(mod m)
i ≡ − r × k − 1 iequiv-rtimes k^{-1} i≡−r×k−1
i − 1 ≡ − k × r − 1 i^{-1} equiv-ktimes r^{-1} i−1≡−k×r−1
整理得
i − 1 ≡ − ⌊ m / i ⌋ × ( m m o d i ) − 1 ( m o d m ) i^{-1}equiv -left lfloor m/i right rfloortimes (m mod i)^{-1} (mod m) i−1≡−⌊m/i⌋×(m mod i)−1 (mod m)
1
2
3
4
5
6
7inv[1] = 1; for(int i = 2; i <= n; ++ i) { inv[i] = ((LL)-m / i * inv[m % i] % m + m) % m; printf("%dn", inv[i]); }
最后
以上就是迅速超短裙最近收集整理的关于求逆元的三种方法的全部内容，更多相关求逆元内容请搜索靠谱客的其他文章。
发表评论 取消回复