逆元：
对于a和p，若 a * inv(a) % p ≡ 1，则称inv(a)为a%p的逆元。其中p为质数
逆元就是在mod下，不能直接除以一个数，而要乘以他的逆元
a * inv(a) = 1 (mod p)
x / a可以改成 x * inv(a) % p

方法一.扩展欧几里得

a * inv(a) = 1 (mod p)
可以变形成 a * inv(a) +k * p = 1(前提是a和p要互素)
可以用扩欧的公式来计算
时间复杂度:O(logn)
适用范围：只要存在逆元即可求，适用于个数不多但是mod很大的时候，也是最常见的一种求逆元的方法。

代码：

ll exgcd(ll a,ll b,ll &x,ll &y)//扩展欧几里得算法
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;  //到达递归边界开始向上一层返回
    }
    ll gcd=exgcd(b,a%b,x,y);
    ll y1=y;    //把x y变成上一层的
    ll x1=x;
    y=x1-(a/b)*y1;
    x=y1;
    return gcd;     //得到a b的最大公因数
}
ll inv(ll a,ll mod){
    ll x,y;
    ll gcd=exgcd(a,mod,x,y);
    if(gcd!=1)return -1;
    else return (x+mod)%mod; 
}

方法二.费马小定理+欧拉定理

费马小定理：假如p是质数，且gcd(a,p)=1，那么 a^(p-1)^ ≡ 1（mod p），进一步可以推出a^p-2^ * a ≡ 1 (mod p)
a^p-2^就是a在mod p意义下的逆元
欧拉函数：a^φ(n)^≡1 (mod n) ，其中 gcd(a,n)=1
若n为素数，φ(n)=n-1
时间复杂度 O(log mod)
适用范围：在mod是素数的时候使用，比扩欧快

代码：

ll poww(ll a,ll b,ll mod){
    ll ans=1;
    ll base=a;
    while(b){
        if(b&1)ans=ans*base%mod;
        base=base*base%mod;
        b>>=1;
    }
    return ans%mod;
}
ll inv(ll a,ll mod){
    return poww(a,mod-2,mod);
}

方法三:递推求逆元

long long inv[maxn];
void init(long long n,long long p)
{
    inv[1]=1;
    for(int i=2;i<=n;i++)
    {
        inv[i]=((p-p/i)*inv[p%i]%p);
    }
}

时间复杂度为O（n）
使用条件：mod为不是很大的素数，且需要多次调用

方法四