当求解公式：(a/b)%m 时，因b可能会过大，会出现爆精度的情况，所以需变除法为乘法：

设c是b的逆元，则有b*c≡1(mod m)；

则(a/b)%m = (a/b)*1%m = (a/b)*b*c%m = a*c(mod m);

即a/b的模等于a*b的逆元的模；

逆元就是这样应用的；

所以逆元的用处可以说是很广的，很有必要掌握

1.费马小定理求逆元

适用范围：一般在mod是个素数的时候用，比扩欧快一点而且好写。

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

2.扩展欧几里得求逆元

适用范围：只要存在逆元即可求，适用于个数不多但是mod很大的时候，也是最常见的一种求逆元的方法。

void exgcd(ll a,ll b,ll& d,ll& x,ll& y){    if(!b) { d = a; x = 1; y = 0; }    else{ exgcd(b, a%b, d, y, x); y -= x*(a/b); }}ll inv(ll a, ll p){    ll d, x, y;    exgcd(a, p, d, x, y);    return d == 1 ? (x+p)%p : -1;}