若
a
⋅
c
=
1
(
m
o
d
b
)
acdot c= 1(modb)
a⋅c=1(modb)，且a与b互质，就定义c为a的逆元，记作
a
−
1
a^{-1}
a−1
也可以叫做c为a在mod p意义下的倒数。
若需求
a
b
(
m
o
d
P
)
frac{a}{b}(modP)
ba(modP)， 可转化为求
b
(
m
o
d
p
)
b(mod p)
b(modp)下的逆元，然后乘
a
a
a，再
m
o
d
P
modP
modP， 即为所求。
即
费马小定理
费马小定理， 只适用于模数为质数的情况，
如果p是一个质数，且a不是p的倍数则有
a
(
p
−
1
)
≡
=
1
(
m
o
d
P
)
a^{(p-1)}equiv=1(modP)
a(p−1)≡=1(modP)
两边同除以a
a
(
p
−
1
)
≡
=
a
−
1
(
m
o
d
P
)
a^{(p-1)}equiv=a^{-1}(modP)
a(p−1)≡=a−1(modP)
所以
a
−
1
≡
=
a
(
p
−
2
)
(
m
o
d
P
)
a^{-1}equiv=a^{(p-2)}(modP)
a−1≡=a(p−2)(modP)
int qmi(int a, int b, int p){
int res = 1;
if(a % p == 0){
res = -1;
}
else{
while (b-2){
if (b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
}
return res;
}
主要借鉴该文章
原创不易
转载请标明出处
如果对你有所帮助 别忘啦点赞支持哈
