求逆元的一些方法总结

求逆元问题是数论中一类比较基础的题目，它常常会与组合数，质数等联系起来。今天我们就来总结一下求逆元的方法，根据数据范围不同有三种，接下来就一一介绍。

-------------------------------------------------------------------------------

方法1.通过扩展欧几里得算法求逆元

这个算法很常见，在这里就不再累述，直接给出代码。

求解ax+by=gcd(a,b)，亦即ax≡1(mod b)。函数返回值是a,b的最大公约数，而x即a的逆元。
注意a, b不能写反了。
gcd(a, b) > 1时逆不存在

 1 int ex_gcd(int a, int b, int &x, int &y) {
 2     int ret, tmp;
 3     if (b == 0) {
 4         x = 1;
 5         y = 0;
 6         return a;
 7     }
 8     ret = ex_gcd(b, a % b, x, y);
 9     tmp = x;
10     x = y;
11     y = tmp - a / b * y;
12     return ret;
13 }

View Code

方法2.通过快速幂求逆元

由于费马小定理，a^(p-1)=1(mod p)-->1/a=a^(p-2)(mod p),故a的逆元为a^p-2.注意这个方法要求模的数必须为质数，传入a和mod-2即可得到结果。

LL quick_inverse(LL n, LL p) {
    LL ret = 1,exponent = p;
    for (LL i = exponent; i; i >>= 1, n = n * n % mod) {
        if (i & 1) {
            ret = ret * n % mod;
        }
    } 
    return ret;
}

View Code

方法3.通过递推求1~n的逆元

我们可以通过inv[i]=inv[p%i]*(p-p/i)%p递推得到逆元。适用于n比较小的情况

1 int inv[N];
2 void get_inverse(int n, int p) {
3     inv[1] = 1;
4     for (int i = 2; i <= n; ++i) {
5         inv[i] = (p - p / i) * inv[p % i] % p;
6     }
7 }

View Code

特殊情况.通过递推求n!

我们可以利用invf[i]=invf[i+1]*(i+1)%p这个公式反递推得到1！~n!的逆元。

 1 int invf[N], factor[N];
 2 void get_factorial_inverse(int n, int p) {
 3     factor[0] = 1;
 4     for (int i = 1; i <= n; ++i) {
 5         factor[i] = i * factor[i - 1] % p;
 6     }
 7     invf[n] = quick_inverse(factor[n], p);
 8     for (int i = n-1; i >= 0; --i) {
 9         invf[i] = invf[i + 1] * (i + 1) % p;
10     }
11 }

View Code

----------------------------------------------------------------------------------

本来想再写一篇组合数的，但肯定没有苟神讲得好，所以直接附上链接：组合数取模

感觉讲得不好，毕竟蒟蒻还不是很能理解里面的内涵，只是总结一下，等用到就不会很无措，大家多多包涵啦。

-END-