逆元

在比赛中我们会遇到形如 (A/B)%MOD 的式子（比如说组合数学中求组合数），但是由于取模对除法没有分配律，所以我们只能乖乖的先算 A/B 再对结果进行取模吗？当A、B较小的时候还行，当A、B很大的时候就不适用了，因为A/B会丢失精度。我们可以将上述式子改写一下 (A/B)%MOD 改为 (A * inv(B)) %MOD 这样一来除法就变为乘法了，这样一来精度就有保证了，上式再进一步改写为 (A%MOD * inv(B) %MOD) % MOD 这里的 inv(B) 就表示B关于MOD的逆元，当GCD(MOD, B) == 1时B才有唯一的逆元。

逆元：对于正整数a和m，如果有a * x = 1 (mod m) 则称 x 为 a 关于 m 的逆元，比如 2 * 3 % 5 = 1, 这样一来就相当于 3 是 2 关于 5 的逆元；

下面介绍几种求逆元的方法

1、费马小定理：

当MOD为素数的时候，会有 inv(B) = pow(B, MOD-2) 这样的公式，这个最好求，我们利用快速幂计算，O(logn)时间复杂度之内就可以求出来结果。

2、扩展欧几里得：(练习扩欧可以试试这个很经典的题目：https://vjudge.net/problem/POJ-1061 )

我们先介绍扩展欧几里得算法，扩欧算法可以求出 ax + by = gcd(a, b) 的一对整数解 (x, y) ，下面是扩展欧几里得算法：

1 //d就是gcd(a,b), (x,y)就是式子 ax+by=gcd(a,b) 的一个解
2 void exgcd(int a, int b, int& d, int& x, int& y){
3     if(!b) { d = a; x = 1; y = 0; }
4     else { exgcd(b, a%b, d, y, x); y -= x*(a/b); }
5 }

这样一来就好办了，这个方程的解 x 就是 a 关于 b 的逆元，就是 b 关于 a 的逆元，但是得注意扩欧求出来的x，y可能是负数或者是0，这个时候我们需要将得到的逆元进行处理，一般是( inv%MOD + MOD ) % MOD

3、欧拉函数：这个先不写了

练习逆元可以试试这题： https://vjudge.net/problem/HDU-1576