在a|b（a能整除b）的前提下，计算（b/a）mod m的时候转化为 计算（b*x）mod m ; 这时的x就是a的逆元（a模m的逆元）；                                 此时x满足  （a*x mod m == 1）；    

这个x的求法有一下两种：
1）扩展欧几里得算法求解 a*x+m*y=1;  因为 a*x mod m == 1   <=>  a*x=1+m1*y   <=>  a*x+m*y==1 ( m=-m1 )。 LL ExGcd(LL a,LL b,LL &x,LL &y){ if(!b) { x=1; y=0; return a; } LL ans=ExGcd(b,a%b,x,y); LL temp=x; x=y; y=temp-a/b*y; return ans; } LL getInverse(LL a,LL p)//a模n的乘法逆元 { if(__gcd(a,p)!=1) return -1; LL x,y; ExGcd(a,p,x,y); return (x+p)%p; }


2）如果有gcd(a,m)==1 ，即a,m互质，则a^(m-1) mod m==1 (这个定理在此不证明，有兴趣去搜）  ;  所以  [ a^(m-2) ] mod m 等价于 a^(-1) ；
      此时a的逆元就是a^(-1)=x = [ a^(m-2) ] mod m 。 LL qpowMod(LL m,LL n,LL p) { LL ans=1; LL temp=m; while(n>0) { if(n&1) ans=ans*temp % p; temp=temp*temp % p; n>>=1; } return ans; } LL _getInverse(LL a,LL p) { return qpowMod(a,p-2,p); }


此外 当a,m不是互质数，计算(b/a)mod m，没办法把b/a转换成b×（a的逆元），可以用  (b/a)mod m == [ b mod (a*m) ] / a 来代替。