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

1.费马小定理：

（此处的p为素数）
证明：

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

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