数论--费马小定理求逆元

ACM常用模板合集

int Fermat_inverse(int a,int mod)
{
    int res = 1;
    for(int i = 1;i < mod - 1;++i) res *= a;
    return res; 
}
 
//如果p为大素数，我们可以用快速幂求解，时间复杂度为：

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); 
}