概述

乘法逆元，一般用于求的值(p通常为质数)，是解决模意义下分数数值的必要手段。
当求解公式：(a/b)%p 时，因b可能会过大，会出现爆精度的情况，所以需变除法为乘法：
设c是b的逆元，则有b*c≡1(mod p);
则(a/b)%p = (a/b)*1%p = (a/b)*b*c%p = a*c(mod p);
即a/b的模等于a*b的逆元的模;
逆元就是这样应用的.

逆元定义

若，且a与p互质，那么我们就能定义: x 为 a 的逆元，记为，所以我们也可以 x 为 a 在  意义下的倒数，所以对于 ，我们就可以求出b在mod p下的逆元，然后乘上a，再 mod p，就是这个分数的值了。

求解逆元的方式

拓展欧几里得

这个方法十分容易理解，而且对于单个查找效率似乎也还不错，比后面要介绍的大部分方法都要快(尤其对于mod p 比较大的时候)。
这个就是利用拓欧求解线性同余方程 a ∗ x ≡ c(mod p) 的c = 1的情况。我们就可以转化为解 a*x + p*y = 1这个方程，求解这个方程的解。不会拓欧可以点这里~
而且这个做法还有个好处在于，当 a ⊥ p(互质)，但p不是质数的时候也可以使用。
代码:

typedef long long ll;
void Exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b)
        x = 1, y = 0;
    else Exgcd(b, a % b, y, x), y -= a / b * x;
}
void INV() {
    ll x, y;
    Exgcd(a, p, x, y);
    x = (x % p + p) % p;
    printf ("%d\n", x); //x是a在mod p下的逆元
}

快速幂

这个做法要利用费马小定理.

若p为素数，a为正整数，且a、p互质。则有。

这个我们就可以发现它这个式子右边刚好为1。
所以我们就可以放入原式，就可以得到：



所以我们可以用快速幂来算出 的值，这个数就是它的逆元了.

代码:

typedef long long ll;
ll _power(ll a, int b, int p) {
    a %= p;
    ll ans = 1;
    while (b) {
        if (b & 1)
            ans = (ans * a) % p;
        a = (a * a) % p;
        b >>= 1;
    }
    return ans;
}
void INV() {
    ll inv = _power(a, p - 2, p); //inv为a在mod p意义下的逆元
    return inv;
}

线性算法

用于求一连串数字对于一个mod p的逆元[洛谷 P3811]。
只能用这种方法，别的算法都比这些要求一串要慢。

首先我们有一个,;
然后设 p=k*i+r,(1<r<i<p)也就是k是 p/i 的商，r是余数。
再将这个式子放到mod p意义下就会得到:

k∗i+r≡0(modp)

然后乘上,就可以得到:

于是，我们就可以从前面推出当前的逆元了。

代码:

void INV() {
    inv[1] = 1;
    for (int i = 2; i <= n; i++)
        inv[i] = (p - p / i) * inv[p % i] % p;
}

阶乘逆元O(n)求

因为有如下一个递推关系。

所以我们可以求出n!n!的逆元，然后逆推，就可以求出1...n!1...n!所有的逆元了。

递推式为inv[i+1]*(i+1)=inv[i].
所以我们可以求出 ​ 的取值了。
然后这个也可以导出 的取值，也就是