逆元的三种求法，1,2求单个，3求多个

1.费马小定理
int qmi(int a,int k,int mod){//快速幂 算a的k次方 
Int res=1;
while(k){
if(k&1/*判断是否为奇数 */) res=(int)res*a%mod;
a=(int)a*a%mod;
k>>=1/*实际上将K除以2*/;
}
return res;
}
Int inv(int a){
Return qmi(a,M-2,M); 
}
2.扩展欧几里得
LL exgcd(LL a,LL b,LL &x,LL &y)//扩展欧几里得算法 
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    LL ret=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return ret;
}
LL getInv(int a,int mod)//求a在mod下的逆元，不存在逆元返回-1 
{
    LL x,y;
    LL d=exgcd(a,mod,x,y);
    return d==1?(x%mod+mod)%mod:-1;
}
3.线性递推
inv[1] = 1;
    for(int i=2;i<=n;i++){
        inv[i] = p - (p / i * inv[p % i] % p) % p;
    }