用费马小定理求逆元

费马小定理(Fermat's little theorem)是数论中的一个重要定理，在1636年提出，其内容为： 假如p是质数，且gcd(a,p)=1，那么 a^(p-1)≡1（mod p），例如：假如a是整数，p是质数，则a,p显然互质(即两者只有一个公约数1)，那么我们可以得到费马小定理的一个特例，即当p为质数时候， a^(p-1)≡1(mod p)。

所以a 的逆元为 a^(p-2);

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll qpow(ll k,ll n,ll mod)
{
    ll ans=1;
    while(n>0)
    {
        if(n%2!=0) ans=ans*k%mod;
        k=k*k%mod;
        n/=2;
    }
    return ans;
}
ll inv(ll n,ll mod)
{
    return qpow(n,mod-2,mod);
}
int main()
{
    ll n,mod;
    scanf("%lld %lld",&n,&mod);
    ll x=inv(n,mod);
    printf("%lld
",x);
    return 0;
}