除法取模需使用费马小定理或者欧拉函数

平常在做组合数相关题型时容易遇到取模的情况，这时候就需要注意到除法取模的注意了。
除法取模不能直接进行除（不清楚怎么说明），需要转化为关于mod的乘积的逆元之后再进行乘法替换除法

---

也就是比如MOD，除数为b
b * b^-1 =（同余) 1 mod MOD
我们就需要乘以那个b^-1,怎么求可以用费马小定理证明b^-1 = b^MOD-2

---

证明：据费马小定理有a, m, 如果gcd(a, m) = 1, 那么 a^MOD-1 =(同余） 1 mod MOD
两边同时乘以a^-1得，a^MOD-2 =(同余) a^-1 mod MOD.

---

所以最后求除法取模等用于乘以b^MOD-2 mod MOD,然后使用快速幂解决
`
int modpower(int a, int b, int mod) {
int res = 1;
a %= mod;
while (b > 0) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}

// 求 n-i 的逆元
int inv = modpower(n - i, mod - 2, mod);
`