模意义下求乘法逆元的各种姿势

2019-04-13 11:40发布

站内文章 / 模拟电子
16435 0 1131

乘法逆元

定义
若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;">