【数论】乘法逆元总结

前言：

我们知道在模意义下的加减乘运算都是具有封闭性的，但除法确是例外，所以我们就要找一种在模意义下代替除法运算的东西
想看代码的在最下方

定义：

如果有 <nobr> ab≡1(modp) </nobr>，则称b是mod p意义下a的乘法逆元。记 <nobr> b=inv（a） </nobr>或 <nobr> b=a−1 </nobr>(定义了剩余系中的除法)

性质：

一个数有逆元的充分必要条件是 <nobr> gcd(a,n)=1 </nobr>，此时逆元唯一存在
<nobr> (ab)modp=((amodp)×(bmodp)modp </nobr>

求法：

1.扩展欧几里得
<nobr> ax≡1(modp) </nobr>可以等价的转化为 <nobr> ax−py=1 </nobr>
然后套用exgcd解方程，并检查 <nobr> gcd（a，p） </nobr>是否等于1
如果 <nobr> gcd（a，p）=1 </nobr>，把 <nobr> x </nobr>调整到 <nobr> 1 </nobr>~ <nobr> p−1 </nobr>即可
复杂度 <nobr> O(log n) </nobr>

2.费马小定理
费马小定理的具体内容和证明请点击这里
由 <nobr> ap−1≡1(mod p) </nobr>得 <nobr> a×ap−2≡1(mod p) </nobr>
所以当模数是一个质数的时候，可以用费马小定理求解，即 <nobr> inv(i)=ip−2(mod p) </nobr>,复杂度 <nobr> O(log n) </nobr>,
3.欧拉定理
由 <nobr> aφ（p）≡1(mod p) </nobr>得 <nobr> aφ（p）−1 </nobr>是a的逆元
适用于模数不是素数
4.递推
<nobr> O（n） </nobr>的时间可以处理出 <nobr> 1 </nobr>~ <nobr> n </nobr>在 <nobr> modp  </nobr>意义下的逆元，方法如下

那么我们就可以做到线性递推

    inv[i]=(mod-mod/i)*inv[mod%i]%mod;

ps：
1.求 <nobr> (ab)modp </nobr>时，如果 <nobr> b×p </nobr>的计算不会爆掉的话，可以转化成
<nobr> a%(b×p)bmodp </nobr>省略求逆元的步骤，还是很方便的
2.在计算组合数时需要用到阶乘的逆元，也可以做到 <nobr> O(n) </nobr>递推，方法如下

fac[0] = 1;
for(int i = 1; i <= MAX; i++)
    fac[i] = (fac[i - 1] * i) % MOD;
inv_fac[MAX] = qpow(fac[MAX], MOD - 2);
for(int i = MAX - 1; i >= 0; i--)
    inv_fac[i] = (inv_fac[i + 1] * (i + 1)) % MOD;

下为几种方法求逆元的代码实现

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
int inv[1000010];

LL ksm(LL a,LL b,LL mod)
{
    int ans=1;
    while(b)
    {
        if(b&1) ans=(ans*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return ans;
} 

LL exgcd(LL a,LL b,LL &x,LL &y)
{
    if(!b)
    {
        x=1;
        y=0;
        return a;
    }
    LL GCD=exgcd(b,a%b,x,y);
    LL tmp=x;
    x=y;
    y=tmp-a/b*y;
    return GCD;
}

LL inv1(LL a,LL mod)//扩展欧几里得求逆元 
{
    LL x,y;
    LL d=exgcd(a,mod,x,y);
    if(d==1) return (x%mod+mod)%mod;
    return -1;
}

LL inv2(LL a,LL mod)//费马小定理
{
    return ksm(a,mod-2,mod);
} 

void inv3(LL mod)//线性递推求逆元 
{
    inv[1]=1;
    for(int i=2;i<=mod-1;i++)
    {
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
        cout<<inv[i]<<" ";
    }
}

int main()
{
    LL n,mod;
    while(cin>>n>>mod)
    {
        cout<<inv1(n,mod)<<" "<<inv2(n,mod)<<endl;
        inv3(mod);
    }
}