逆元的意义及求法

逆元的意义：

通俗的讲，逆元可以看做一个数的倒数的整数形式，但是一个数的逆元在不同的$ (mod)$ 意义下是不一样的。

\(a*x\equiv1 \mod n\) ?\(a*\frac{1}{a}\equiv1 \mod n\)

这个方程便是逆元的真正定义，$ x$ 的解即代表$ a$ 在$ \mod n$ 意义下的逆元，通俗的讲：此时的$ x$ 就相当于$ a$ 的倒数，这样$ a*x$ 便会等于1，在\(\mod n\) 意义下余数必定为一。当然这个式子要建立在$ a$ 与$ n$ 互质的基础上！

可是逆元有什么用呢？直接用倒数不行吗？这是因为我们发现一个分数$ mod$ 一个整数时是不能直接模运算的，但是可以进行乘法运算，我们就要用到逆元（一个数倒数的整数形式）

就像：$ \frac{a}{b}\mod (n)$ \(\not =\) $ \frac{a\mod n}{b\mod n}\mod (n)$ 但是：$ \frac{a}{b}\mod (n)$ \(=\) $ a*b^{-1}\mod (n)$

所以当除运算碰上我们的模运算时，我们就需要$ \mod 模数$ 意义下的逆元了！

单个逆元的求法：

1. 费马小定理：

对于整数$ a$ 与质数$ p$ ，若$ a$ 与$ p$ 互质，则有：$ a^{p-1}\equiv1 \mod p$

我们将上述定理稍稍变一下：$ a*a^{p-2}\equiv1 \mod p$ （这不就是我们的逆元定义式吗？）

所以$ a^{p-2}$ 就是$ a$ 在$ \mod p$ 意义下的逆元啊！这个我们用快速幂求一下不就行了吗！

inline ll fast(ll x){//求x在%mod意义下的逆元
    int y=mod-2;ll res=1;
    while(y){
        if(y&1)res=res*x%mod;
        x=x*x%mod; y>>=1;
    }return res;
}

2. 拓展欧几里得：

用快速幂求逆元，是敌不过某些毒瘤出题人，比如模数就是个long long，这样快速幂就会溢出。这个时候怎么办？嗯，我们的万能$ gcd$ 就要登场了！

1. 存在整数$ x_1$ 和$ y_1$ ，使得：\(x_1*a+y_1*b=gcd(a,b)\)
2. 同理，存在整数$ x_2$ 和$ y_2$ ，使得：\(x_2*b+y_2*(a\mod b) =gcd(b,a\mod b)\)

根据我们万能$ gcd$ 的性质，上述两个等式的右半部分相同，同理它们的左半部分也相同！

得到：

1.\(x_1*a+y_1*b=x_2*b+y_2*(a\mod b)\)
2.\(x_1*a+y_1*b=x_2*b+y_2*(a-\frac{a}{b}*b)\)
3.\(x_1*a+y_1*b=y_2*a+(x_2-y_2*\frac{a}{b})*b\)
4.\(x_1=y_2\) $ y_1=x_2-y_2*\frac{a}{b}$

所以我们根据$ x_2$ 和$ y_2$ 就能求出$ x_1$ 和$ y_1$ 辣！而众所周知的，我们$ gcd$ 大法的终极形态就是当$ b==0$ 的时候，这时我们的$ x=1$ ，而因为$ b==0$ ，所以我们的$ y$ 随便取一个就行（好像都用0的），然后我们在回溯的时候，不断往前推我们的$ x$ 和$ y$ ，直到得出我们最初的哪一组解。（这其实就是一个构造的过程）

可是这和求逆元又有什么联系呢？我们发现只有当我们的 \(a\) 与\(b\) 互质的时候即 \(gcd(a,b)=1\) 时，这个二元一次方程不就变成了： \(x_1*a+y_1*b=1\) （等同于 \(x_1*a=1(\mod b)\) 或 \(y_1*b=1(\mod a)\) ）而这，不就相当于我们逆元的定义式吗？我们再用上述方法将 \(x_1\) 和 \(y_1\) 求出来，不就是逆元了吗？

inline int exgcd(int a,int b,int &x,int &y){
    if(b==0)return x=1,y=0,a;
    int d=exgcd(b,a%b,y,x);
    y-=(a/b)*x; return d;
}

递推求多个逆元：

上面我们说的是单个求逆元的方法，复杂度为$ O(logn)$ 级别（一般快速幂要快一些），可是有一些题目往往需要我们求多个逆元（如连续的数，阶乘，和次方的逆元），而且单个求的时间往往要在$ O(1)$ 的复杂度，我们有没有办法$ O(n)$ 求出所有这些逆元呢？答案是可以的，但只能是一些特殊的数。

线性求逆元：

同余是神奇的，我们可以通过它推出一个逆元的递推式：

$ \Rightarrow inv[i]=(m-m/i)*inv[m%i]%m$

推导过程：设$ a=m/i$ ，设$ b=m%i$ ，则有$ m=a*i+b$

$ \Rightarrow a*i+b\equiv 0\mod(m)$

$ \Rightarrow -a*i\equiv b\mod(m)$

我们将同余号两边都除以一个$ i*b$ ，把逆元这个概念引进来，得到：

$ \Rightarrow -a*inv[b]\equiv inv[i]\mod(m)$

这样，我们就将$ i$ 和$ m%i$ 联系到了一起，我们将$ a$ 和$ b$ 换回原装可得：

$ \Rightarrow -m/i*inv[m%i]\equiv inv[i]\mod(m)$

$ \Rightarrow inv[i]\equiv (m-m/i)*inv[m%i] \mod(m)$

$ \Rightarrow inv[i]=(m-m/i)*inv[m%i] %m$

这样，只要我们预处理一下$ inv[1]=1$ ，往后的所有逆元我们都能线性求了！

int main(){
    n=qr(),m=qr(); inv[1]=1;
    for(int i=2;i<=n;i++)
        inv[i]=(ll)(m-m/i)*inv[m%i]%m;
    return 0;
}

线性求阶乘逆元： （这个比上面的要简单一些。）

我们都知道，阶乘代表：\(n!=1*2*3...*n\) ，那么我们可以得出：\((n-1)!=n!/n\)

这不也是一个逆元式吗？只不过我们要到这递推而已。

我们先用快速幂或拓展欧几里得求出$ n!$ 的逆元，然后所有比它小的逆元都可以线性推过去了！

int main(){
    n=qr(),m=qr(); jc_inv[n]=1;
    for(int i=n;i>=2;--i)
        jc_inv[i-1]=(ll)jc_inv[i]*i%m;
    return 0;
}

逆元的意义及求法

原文：https://www.cnblogs.com/812-xiao-wen/p/10500580.html