概念
如果一个线性同余方程 ax === 1 (mod b) ，则 x 称为 a mod b 的逆元。
那么求逆元之前我们还要先明白什么是线性同余方程：
形如 ax === b (mod c) 的方程被称为线性同余方程。
线性同余方程有以下性质：
1. 方程 ax + by = c 与方程 ax === c (mod b) 是等价的，有整数解的充要条件为 gcd(a,b)|c 。
2. 若 gcd(a,b)=1 ，且 x1, y1 为方程 ax + by = c 的一组解，则该方程的任意解可表示为： x=x1+bt, y=y1-at 且对任意整数 t 都成立。
那么求一个线性同余方程怎么求呢？
我们可以使用扩展欧几里得算法：
扩展欧几里德定理，常用于求 ax + by = gcd(a, b) 的一组可行解。
我们首先设x1, y1, x2, y2满足以下条件
ax1 + by1 = gcd(a, b)
bx2 + (a mod b)y2 = gcd(b, a mod b)
然后，由欧几里得定理我们可以知道gcd(a, b)是等价于gcd(b, a mod b)的。也就是说上面的方程组可以变成：
ax1 + by1 = gcd(a, b)
bx2 + (a mod b)y2 = gcd(a, b)
即 ax1 + by1 = bx2 + (a mod b)y2
再将(a mod b)展开为(a - (floor(a / b) * b))
最终变形可得到 x1 = y2, y1 = x2 - floor(a / b)y2
如此往复下去，y的系数将会降至0，而此时x的值为1，y值为0。
可得递归起始点：
if (!b) {
x = 1;
y = 0;
}此时的a是gcd值，我们把gcd值向上抛出，则整个递归函数如下：
int ext_gcd(int a, int b, int &x, int &y) { // x，y均使用引用传递，可以直接在函数内更改对应的值
if (!b) {
x = 1;
y = 0;
return a; // 向上抛出
}
int d = ext_gcd(b, a % b, x, y); // d接受的是gcd的值
int t = x; // 这里的t是x2，y是y2
x = y; // 即x1 = y2
y = t - (a / b) * y;// 即y1 = x2 - floor(a / b)y2
return d; // 向上抛出
}这样有什么意义呢？
我们得到了ax + by = gcd(a, b)中的x1和y1
要求的是ax + by = c因为它和ax === c (mod b)等价
所以我们就对等式两边同除以gcd(a, b)
等式变成了a(x1/gcd(a, b)) + b(y1/gcd(a, b)) = 1
然后乘上c
就得到了a(cx1/gcd(a, b)) + b(cy1/gcd(a, b)) = c
所以原方程的一个解：x = cx1/gcd(a, b), y = cy1/gcd(a, b)
代码如下：
// 返回值表示是否有解，解会直接更新为x，y的值
bool line_eq(int a, int b, int c, int& x, int& y) {
int d = ext_gcd(a, b, x, y);
if (c % d != 0)
return 0;
int k = c / d;
x *= k;
y *= k;
return 1;
}学会了求线性同余方程我们就可以来学习求逆元了。
由于逆元的特殊性，ax === 1 (mod b)事实上会等价于一个方程ax + by = 1
所以可以简单地把上文的参数直接设置为1，此处不再赘述。
此时注意到有费马小定理：若p为一个素数且a，p互质，则pow(a, p-1) === 1 (mod p)
和ax === 1 (mod b)联立可以得到ax === pow(a, b-1) (mod b) (mod b)。
消去多余的(mod b)以及消去等式两边的a可得x === pow(a, b-2) (mod b)所以要求x只需求模b意义下的pow(a, b-2)即可。
所以可以直接调用快速幂fast_pow_mod(a, b-2, b)
前面学会了求乘法逆元，而组合数是一个经常需要用到乘法逆元的地方。话不多说直接分析。
对于C(a, n) % p，它可以转化为(n! %p / (m! % p * (n-m)! % p)) % p。乘法是可以直接对两个因子都模p的，但是除法不能。所以这里我们要把它转化为乘法。乘法逆元就派上用场了。
首先求得m! % p的乘法逆元M，(n-m)! % p的乘法逆元N_M
此式子将转化为：((n! * M) % p * N_M) % p
于是，所有的问题都只需要求阶乘就可解决。