求逆元

求逆元

逆元

求一个数的逆元，就是说这个数乘以它的逆元恰好等于1。在 \(\mathbb{Z}_p\) 内，设 \(a\),\(b\) 互质，则 \(a\) 的逆元记作 \(a^-1\)，定义为 \(b\)，使得 \(ab=1\)。

\(p\) 是素数时，逆元唯一存在。

\(p\) 是合数时，逆元可能不存在。

扩展欧几里得

适用于 \(p\) 不为素数的情况。

解方程组 \(ax+py=1\)，解得的 \(x\) 即为 \(a\) 的逆元。

费马小定理

费马小定理：若 \(p\) 为素数，则对于任意整数 \(a\)，有

\[a^{p-1}\equiv 1\pmod p,\]

那么

\[a^{p-2}\equiv a^{-1}\pmod p.\]

递推

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

#include<iostream>
using namespace std; 
int inv[20],n=10,MOD=7;
int main()
{
    inv[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(i>=MOD)break;
        inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD; 
    }
    for(int i=1;i<=n;i++)
    {
        cout<<inv[i]<<"\n";
    }
    return 0;
}

求阶乘的逆元

mul[0]=inv[0]=1;
for(int i=1;i<=n;i++) mul[i]=1ll*mul[i-1]*i%mod;
inv[n]=fpow(mul[n],mod-2,mod);  //这里 inv 表示的是阶乘的逆元
for(int i=n-1;i>0;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod;