1.扩展欧几里得求逆元

typedef long long ll;//ax + by = gcd(a,b)//传入固定值a,b.放回 d=gcd(a,b), x , yvoid extendgcd(ll a,ll b,ll &d,ll &x,ll &y){    if(b==0){d=a;x=1;y=0;return;}    extendgcd(b,a%b,d,y,x);    y-=x*(a/b);}//Ax=1(mod M)，gcd(A,M)==1//输入：10^18>=A,M>=1//输出：返回x的范围是[1,M-1]ll GetNi(ll A,ll M){    ll rex=0,rey=0;    ll td=0;    extendgcd(A,M,td,rex,rey);    return (rex%M+M)%M;}

2.根据欧拉定理求逆元,当mod素数时可以速度较快。

//a^b%mod 快速幂long long Quk_Mul(long long a,long long b,long long mod){    long long qsum=1;    while(b)    {        if(b&1) qsum=(qsum*a)%mod;        b>>=1;        a=(a*a)%mod;    }    return qsum;}//欧拉函数:复杂度O(n^(0.5)),返回[1,n-1]中所有和n互素的数的个数和ll phi(ll x){    ll sum=x;    for(ll i=2;i*i<=x;i++)    {        if(x%i==0)        {            sum=sum-sum/i;            while(x%i==0) x/=i;        }    }    if(x!=1) sum=sum-sum/x;    return sum;}//Ax=1(mod M)，gcd(A,M)==1//输入：10^18>=A,M>=1//输出：返回x的范围是[1,M-1]//复杂度：如果M是素数，则直接用M-2代替phi(M)-1 复杂度为O(logM)//       如果M不是素数，则复杂度为O( M^(0.5) ) 好慢。ll GetNi(ll A,ll M){    //return Quk_Mul(A, phi(M)-1, M);    return Quk_Mul(A, M-2, M);}

3.对于a/b (mod m),不要求b和m互质。前提当然b能整除a

(a/b) % m等于a%(b*m)/b

只要是bm不需要高精度，这种方法是很好用的。

证明还是很好证的：

(a/b) mod m = a/b – k*m = (a – k*b*m)/b =(a%(b*m))/b;