概述
计 算 逆 元 的 三 种 方 法 计算逆元的三种方法 计算逆元的三种方法
一、首先是两种O(log)时间求单个数的逆元
我们要求
a
a
a在模
p
p
p意义下的逆元
其中
a
a
a是小于
p
p
p的正整数，
p
p
p是一个素数
① 费马小定理：
由费马小定理
a
p
−
1
≡
1
(
m
o
d
p
)
a^{p-1}≡1 (mod p)
ap−1≡1 (mod p)可以得到：
a
⋅
a
p
−
2
≡
1
(
m
o
d
p
)
acdot a^{p-2}≡1 (mod p)
a⋅ap−2≡1 (mod p)
所以可以直接使用快速幂求出
a
p
−
2
a^{p-2}
ap−2即为
a
a
a在模
p
p
p意义下的逆元
② 扩展欧几里得：
先假设我们要求的
a
a
a在模
p
p
p意义下的逆元为
x
x
x
可以得到方程
a
⋅
x
≡
1
(
m
o
d
p
)
acdot x≡1 (mod p)
a⋅x≡1 (mod p)
变成一般等式：
a
⋅
x
+
p
⋅
y
=
1
acdot x+pcdot y=1
a⋅x+p⋅y=1
现在要求的就是
x
x
x
p
p
p是素数，所以
g
c
d
(
a
,
p
)
=
1
gcd(a,p)=1
gcd(a,p)=1，可以使用扩展欧几里得计算得到
x
x
x。
二、线性求逆元：
显然
1
−
1
=
1
1^{-1}=1
1−1=1
假设现在已经计算出
i
i
i之前的所有正整数的逆元
现在要求
i
i
i的逆元
先写出等式：
i
⋅
k
+
r
=
p
icdot k+r=p
i⋅k+r=p
变成模
p
p
p下的恒等式：
i
⋅
k
+
r
≡
0
(
m
o
d
p
)
icdot k+r≡0 (mod p)
i⋅k+r≡0 (mod p)
两边同乘
i
−
1
⋅
r
−
1
i^{-1}cdot r^{-1}
i−1⋅r−1得到：
k
⋅
j
−
1
+
i
−
1
≡
0
(
m
o
d
p
)
kcdot j^{-1}+i^{-1}≡0 (mod p)
k⋅j−1+i−1≡0 (mod p)
移相：
i
−
1
≡
−
k
⋅
j
−
1
(
m
o
d
p
)
i^{-1}≡-kcdot j^{-1} (mod p)
i−1≡−k⋅j−1 (mod p)
k
k
k和
j
j
j可以分别用
p
/
i
p/i
p/i和
p
%
i
p%i
p%i来代替：
i
−
1
≡
−
(
p
/
i
)
⋅
(
p
%
i
)
−
1
(
m
o
d
p
)
i^{-1}≡-(p/i)cdot (p%i)^{-1} (mod p)
i−1≡−(p/i)⋅(p%i)−1 (mod p)
取
正
数
：
i
−
1
=
(
p
−
p
/
i
)
⋅
(
p
%
i
)
−
1
%
p
取正数：i^{-1}=(p-p/i)cdot (p%i)^{-1}%p
取正数：i−1=(p−p/i)⋅(p%i)−1%p
p
%
i
<
i
p%i<i
p%i<i 所以
p
%
i
p%i
p%i的逆元已经算出来了，右端项没有未知数。所以就可以
O
(
n
)
O(n)
O(n)的时间内算出
1
−
n
1-n
1−n之内所有数的逆元了
inv[1] = 1;
for(int i = 1; i <= n; i++)
inv[i] = (p-p/i)*inv[p%i]%p;
最后
以上就是体贴世界为你收集整理的计算逆元的三种方法 计 算 逆 元 的 三 种 的全部内容，希望文章能够帮你解决计算逆元的三种方法 计 算 逆 元 的 三 种 所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复