『算法-ACM竞赛-数学-数论』费马小定理+求逆元

『算法-ACM 竞赛-数学-数论』费马小定理+求逆元

1.费马小定理:


(此处的 p 为素数)
证明:

费马小定理求逆元
如果 p 为小素数我们选择直接暴力,时间复杂度为:

1
2
3
4
5
6
int Fermat_inverse(int a,int mod)
{
int res = 1;
for(int i = 1;i < mod - 1;++i) res *= a;
return res;
}
CPP

如果 p 为大素数,我们可以用快速幂求解,时间复杂度为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
long long fast_pow_mod(long long a,long long b,long long mod)
{
long long res = 1;
while(b){
if(b & 1) res = (res * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return res;
}
long long Fermat_inverse(long long a,long long mod)
{
return fast_pow_mod(a,mod - 2,mod);
}
CPP

『算法-ACM竞赛-数学-数论』费马小定理+求逆元
https://chiamzhang.github.io/2024/06/29/『算法-ACM竞赛-数学-数论』费马小定理+求逆元/
Author
Chiam
Posted on
June 29, 2024
Licensed under
Powered By Valine
v1.5.1