逆元

若ax≡1 (mod p) 则称x为a模p意义下的逆元，记为a^(-1)

如何求逆元？

1、线性求逆元

递推：

inv[0]=inv[1]=1;
for(int i=2; i<=n; i++) {
  inv[i]=(-(Mo/i)*inv[Mo%i])%Mo;
} 

递归：

int inv(int x) {
 if(x==0 || x==1) return 1;
 return (-(Mo/i)*inv(Mo%i))%Mo;
}

2、logMo求单个逆元 （Mo为模数）

int inv(int x) {
 int y=Mo-2,ret=1;
 while(y) {
   if(y&1) (ret*=x%Mo)%=Mo;
   x=x*x%Mo,y>>=1;      
 }       
 return ret;   
}

根据费马小定理：a^(p-1)≡1 (mod p) 即a^(p-2) 就是a模p意义下的逆元，快速幂计算即可