欧拉定理：

a ^ temp[p] = 1   (mod p);  //当a 与 p 互质 , temp[p] 的含义是 p 的欧拉函数的值

费马定理： 当p也为质数的时候

a ^ (p - 1) = 1    (mod p);  // a与p互质，且p为质数。当p为质数时，temp[p] == p - 1;

适用题型：

1.可以用于求逆元的时候

原理：

a / b %  mod == a * ( b ^ (-1) )% mod;

将1 / b 用( b ^ -1 ) 代替

求% mod下  b ^ -1对应的值。

a / b * b % mod == a * (b ^ （-1）) * b % mod ;

---> a % mod == a * (b ^ (-1) ) * b % mod;
---> 1 % mod == (b ^ -1) * b % mod;

当mod为质数 且 b 与 mod互质的时候，

b ^ (temp[mod]) == 1  ( % mod);
--->  b ^ (mod - 1) == 1 (% mod);

由上面推导出的1 % mod == (b ^ -1) * b % mod;  和b ^ (mod - 1) == 1 (% mod);

(b ^ -1) * b % mod == b ^ (mod - 1) % mod;

所以(b ^ -1) % mod == b ^ (mod - 2) % mod;

所以逆元b ^ -1  == b ^ (mod - 2);  

代码实现

如果p在此时为质数，则 qmi(int a ,int  b , int mod) // b == mod - 2;  

qmi(a,mod - 2 , mod); 

int qmi(int a , int b , int mod)
{
    int res = 1;
    while(b)
    {
        if(b & 1)
        {
            res = (long long)res * a % mod; 
        }
        b >>= 1;
        a = (long long)a * a % mod;
    }
}

而当对应的mod 不是质数的时候，则不能用费马定理，但是可以用欧拉定理

a ^ temp[p] = 1   (mod p);  //当a 与 p 互质 , temp[p] 的含义是 p 的欧拉函数的值

a % mod 下的逆元即为：
qmi(a , temp[mod] - 1 , mod);