推荐https://blog.csdn.net/qq_37656398/article/details/81434277
这几所说的乘法逆元其实是 模反元素(也叫模逆元)

  a  *  a^-1  ≡ 1（mod p）（p为素数）   

方法一， 扩展欧几里得求逆元：

扩展欧几里得，可以求逆元的原因：

假设a 与 x互逆（mod p）：
         a * x %p = 1；
         等价于：
          ax = py+1；
          ax- py = 1;
         这样就可以用扩展欧几里得解线性不定方程求逆元了

ll exgcd(ll a, ll b, ll &x, ll &y)// ax+by == gcd(a, b)
{
    ll res;
    if(b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    res = exgcd(b,a%b, x, y);

    ll tmp = y;
    y =  x- a/b*y;
    x = tmp;
    return res;
}
ll mod_reverse(ll a, ll mod)
{
    ll x, y, d;
    d = exgcd(a, mod, x, y);

    if(d == 1)// 有解
    {
        /**求 大于0的最小特解******/
        if(x%mod <= 0)return x%mod+mod;// 其实模的是 mod/d， 但是d == 1, 所以这个两个值相等
        else return x%mod;
    }
    else return -1ll;//(long long)-1;// 无解

}

方法二 费马定理求乘法逆元：

  费马小定理:
        如果p是一个质数，而整数a不是p的倍数，则有a^（p-1）≡1（mod p）

所以a* a^p-2 ≡ 1(mod p);
所以 a的逆元 就是 a ^ p- 2(mod p)

using namespace std;
long long pow_mod(long long a, long long b)
{
    long long ret = 1;

    while(b)
    {
        if(b%2!= 0)ret*=a%Mod;//b&1;
        a =a*a%Mod;
        b/=2;//b>>1
    }
    return ret;
}
调用时：
 pow_mod(a, Mod-2);

求地推求阶乘的逆

    int f[maxn];//阶乘数组
    int inv[maxn];// 逆元数组
    f[0]=1;// 
    for(int i=1; i<=N; i++)//
        f[i]=f[i-1]*i%Mod;
    inv[0]=1;
    
    inv[N]=PowMod(f[N],Mod-2);// 先用费马 求 N！的逆元
    
    for(int i=N-1; i>0; i--)// 地推求 i！的逆元
        inv[i]=inv[i+1]*(i+1)%Mod;// i阶乘的 逆 就等于 inv阶乘的逆成i+1.

地推求连续数的逆元

int inv[maxn]; //逆元数值
inv[1] = 1;//1的逆元时1

for(int i = 2;i<= N;i++)// N为要求逆元的上限
{
	inv[i] = (Mod - Mod/i)*inv[Mod%i] %Mod;
}

证明：

https://www.cnblogs.com/Lates/p/11147053.html

　　　　递推式：inv(i)=(p−p/i)×inv(pmodi)modp
　　　　证明过程：

　　　　　　假设该式成立，则有

　　　　　　　　　　 i×inv(i) ≡i×(p−⌊pi⌋)×inv(pmodi) modp
　　　　　　变式后可得

　　　　　　　　　　i×inv(i)≡(ip−i×⌊pi⌋))×inv(pmodi)modp
　　　　　　根据随时取模性质，得到
　            	  i×inv(i)≡ (p*(i-1) + p-i×⌊pi⌋ )×inv(pmodi) mod p
　　　　　　　  　　i×inv(i)≡(pmodi)×inv(pmodi)modp　
　　　　　　　　
　　　　　　显然，这个式子是成立的