模意义下求乘法逆元的各种姿势
2019-04-13 11:40发布
生成海报
乘法逆元
定义
若
ax≡1modp" role="presentation" style="position: relative;">ax≡1modp,则称
x" role="presentation" style="position: relative;">x是
a" role="presentation" style="position: relative;">a在
modp" role="presentation" style="position: relative;">modp意义下的逆元,记为
x≡a−1modp" role="presentation" style="position: relative;">x≡a−1modp
当然,
a" role="presentation" style="position: relative;">a也是
x" role="presentation" style="position: relative;">x在
modp" role="presentation" style="position: relative;">modp意义下的逆元
ab=a⋅b−1" role="presentation" style="position: relative;">ab=a⋅b−1
几乎所有模意义下的除法都需要逆元
有逆元的充要条件
a" role="presentation" style="position: relative;">a在
modp" role="presentation" style="position: relative;">modp意义下有逆元的充要条件:
(a,p)=1" role="presentation" style="position: relative;">(a,p)=1
逆元的求法
EXGCD
若求
a" role="presentation" style="position: relative;">a在
modp" role="presentation" style="position: relative;">modp意义下的逆元,则可以转化为求解如下方程
ax+py=1" role="presentation" style="text-align: center; position: relative;">ax+py=1
有EXGCD的相关知识可以得到,当且仅当
(a,p)=1" role="presentation" style="position: relative;">(a,p)=1时有解(有逆元的充要条件的证明)
费马小定理
如果
p" role="presentation" style="position: relative;">p为质数,则
ap−1≡1modp" role="presentation" style="position: relative;">ap−1≡1modp
∴a⋅ap−2≡1" role="presentation" style="position: relative;">∴a⋅ap−2≡1
∴ap−2≡a−1" role="presentation" style="position: relative;">∴ap−2≡a−1
欧拉定理
将费马小定理中的
p−2" role="presentation" style="position: relative;">p−2换为
φ(p)−1" role="presentation" style="position: relative;">φ(p)−1即可
p" role="presentation" style="position: relative;">p可以不是质数
递推
用于
O(n)" role="presentation" style="position: relative;">O(n)预处理
[1⋯n]" role="presentation" style="position: relative;">[1⋯n]的逆元
构造
p=ki+r" role="presentation" style="position: relative;">p=ki+r
∴ki+r≡0modp" role="presentation" style="position: relative;">∴ki+r≡0modp
∴ki=−r" role="presentation" style="position: relative;">∴ki=−r
∴i−1=−k⋅r−1" role="presentation" style="position: relative;">∴i−1=−k⋅r−1
其中
k=⌊pi⌋,r=p%i" role="presentation" style="position: relative;">k=⌊pi⌋,r=p%i
∴i−1=−⌊pi⌋⋅inv[p%i]" role="presentation" style="position: relative;">∴i−1=
打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮