我们知道，在模意义下，加减乘运算是封闭的; 例如在模17意义下，8+11=((8%17)+(11%17))%17=2，19+21=((19%17)+(21%17))=6; 减法同理，但是在C++编译器中取模的意义是与数学上不同的，负数mod正数应该是非负数，但是C++却可能模出负数，所以我们要多加一些处理，对于x,可以(x%mod+mod)%mod保证其正确性，比如在模17意义下，21-19=((21%17)-(19%17))=2,35-21=((35%17)-(21%17))=14. 乘法也是这样，先模再乘，乘完再模，其意义不会变化。 但是除法不是。 于是我们需要用到除法逆元。 关于逆元的定义。 定义 对a∈Zm，存在b∈Zm，使得a+b ≡ 0 (mod m)，则b是a的加法逆元， 记b= - a。
定义 对a∈Zm，存在b∈Zm，使得a×b ≡1  (mod m)，则b为a的乘法逆元  ，记b=1/a; 加法逆元很少用啊，那么怎么求乘法逆元呢？ 方法一：我们要找到a×b ≡1  (mod m)的b，所以很容易想到用扩展欧几里得求出a*b+m*y=1的一组解，b就是a在模m意义下的乘法逆元。当然前提是a与m互质，因为只有这样gcd(a,m)才是1 ll exgcd(ll a,ll b,ll &x,ll &y) { if(b==0) { x=1; y=0; return a; } int r=exgcd(b,a%b,x,y); ll t=y; y=x-(a/b)*y; x=t; return r; } ll inv(ll a) { ll x,y; ll r=exgcd(b,mod,x,y); if(r==1) return (x%mod+mod)%mod; return -1; }
方法二：根据费马小定理，a^(p-1)≡ 1(mod p)  所以稍加变形，a*a^(p-2)≡ 1(mod p)  即a^(p-2)是a在模p意义下的乘法逆元。 快速幂一下就好了，复杂度O(log p) 方法三：O(n)线性预处理 inv[1]=1; for(int i=2;i<=n;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;可以再推一遍求出阶乘的逆元。

求出逆元之后，要求(a/b)%mod, 设b`为b在模mod意义下的逆元，直接(a%mod*b`%mod)%mod即可。