前言
逆元是模运算中很常用的计算方式，非常重要，是很多数论的辅助算法。
定义
在模 \(m\) 的意义下找到一个数 \(x\) 使得 \(ax\equiv 1\pmod m\)，则称 \(x\) 是 \(a\) 在模 \(m\) 的意义下的逆元，记作 \(inv(a)\)。
特别的，当 \(m\mid a\) 时，逆元不存在。
逆元的性质:
\[a/b\equiv a\times inv(b)\pmod m
\]
由于这一点性质，我们可以在模意义下进行一边取模一边计算的除法运算，将模意义下的运算扩充到了除法，是非常常用的数论基础算法。
求法
第一境界：扩展欧几里得
由
\[ax\equiv 1 \pmod b
\]
得
\[ax+by=1
\]
这样就转化成了裴蜀等式，扩展欧几里得算法 解决。
#include
using namespace std;
int n,a,b,x,y;
int exgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
int r=exgcd(b,a%b,x,y);
int d=x;
x=y;
y=d-a/b*y;
return r;
}
int main()
{
scanf("%d%d",&a,&b);
int r=exgcd(a,b,x,y);
printf("%d\n",(x+b)%b);
return 0;
}
时间复杂度：\(O(\log n)\)
第二境界：费马小定理
费马小定理：对于两个正整数 \(x,p\)，若 \(\gcd(x,p)=1\) 且 \(p\) 为质数，则有如下关系式：
\[x^p\equiv x\pmod p
\]
根据费马小定理，我们可以推出以下式子：
\[x^{p-1}\equiv 1\pmod p
\]
\[x\times x^{p-2}\equiv 1\pmod p
\]
结合逆元的定义式，此时 \(x\) 的逆元为 \(x^{p-2}\)。
#include
using namespace std;
long long n,p;
long long fast_power(long long a,long long p,long long m)
{
long long x=a,ans=1;
while(p)
{
if(p%2==1)ans=ans*x%m;
p/=2;
x=x*x%m;
}
return ans;
}
int main()
{
scanf("%lld%lld",&n,&p);
printf("%lld\n",fast_power(n,p-2,p));
return 0;
}
时间复杂度：\(O(\log n)\)
第三境界：线性递推
首先，一定有下面递推式：
\[inv(1)\equiv 1\pmod p
\]
设 \(k=\lfloor \frac{p}{i}\rfloor,r=p\bmod i\)，则有下面式子：
\[k\times i+r\equiv p\equiv0\pmod p
\]
等式两边同时乘以 \(inv(i),inv(r)\)，得到：
\[k\times i\times inv(i)\times inv(r)+r\times inv(i)\times inv(r)\equiv 0\pmod p
\]
由逆元的性质得到：
\[i\times inv(i)\equiv 1\pmod p
\]
\[r\times inv(r)\equiv 1\pmod p
\]
所以综合上述三式得到：
\[k\times inv(r)+inv(i)\equiv 0\pmod p
\]
移项得：
\[inv(i)\equiv -k\times inv(r)\pmod p
\]
展开上式得：
\[inv(i)\equiv -\lfloor \frac{p}{i}\rfloor\times inv(p\bmod i)\pmod p
\]
这已经是逆元的递推式了。
又因为 \(r=p\bmod i\)，得到 \(r #include using namespace std; long long n,p,inv[3000010]; int main() { scanf("%lld%lld",&n,&p); inv[1]=1; for(int i=2;i<=n;i++) inv[i]=((p-p/i)*inv[p%i])%p; for(int i=1;i<=n;i++) printf("%lld\n",inv[i]); return 0; } 时间复杂度（总体）：\(O(n)\) 时间复杂度（均摊）：\(O(1)\) 小 trick：线性求阶乘逆元 首先用扩展欧几里得或费马小定理求出最后一项阶乘的逆元，然后从后往前递推。记 \(inv[i]\) 为 \(i!\) 的逆元，易得如下递推式： \[inv[i]=inv[i+1]\times(i+1) \] 因为 \(inv[i+1]\) 中必然包含 \(i+1\) 的逆元，所以乘以 \(i+1\) 之后刚好抵消。而此时的 \(inv[i+1]\) 不存在 \(i+1\) 了，就只剩下 \(1\) 到 \(i\)，就是 \(inv[i+1]\)。这样就可以在 \(O(n)\) 的时间内求出阶乘逆元。 例题 例题 \(1\) ： P3811 【模板】乘法逆元 如第三境界：线性递推，不多赘述。 #include using namespace std; long long n,p,inv[3000010]; int main() { scanf("%lld%lld",&n,&p); inv[1]=1; for(int i=2;i<=n;i++) inv[i]=((p-p/i)*inv[p%i])%p; for(int i=1;i<=n;i++) printf("%lld\n",inv[i]); return 0; } 例题 \(2\) ： P5431 【模板】乘法逆元 2 暴力通项分数相加，得到这个式子： \[s=\sum^{n}_{i=1}\prod^{i-1}_{j=1}a_j\times\prod^{n}_{j=i+1}a_j\times k^{i} \] \[z=\prod^{n}_{i=1}a_i \] \[ans=\frac{s}{z} \] 做出以下定义： \[q_i=\prod^{i}_{j=1}a_j,h_i=\prod^{n}_{j=i}a_j \] 易得以下递推式：（可在 \(O(n)\) 内进行预处理） \[q_i=q_{i-1}\times a_i \] \[h_i=h_{i+1}\times h_i \] 最后直接套用预处理的数据，可以在 \(O(n)\) 的时间内计算出 \(s\)。最后运用逆元求出结果。 \[ans=\sum^{n}_{i=1}q_{i-1}h_{i+1}k^{i}-inv(q_n) \] 注意读入数据时需要使用快读卡常。慢了 1ms 的记录 #include using namespace std; int n,p,k,a[5000010],q[5000010],h[5000010],ans=0; inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} return x*f; } long long power(long long a,long long p,long long m) { long long x=a,ans=1; while(p) { if(p%2==1)ans=ans*x%m; p/=2; x=x*x%m; } return ans; } int main() { n=read();p=read();k=read(); for(int i=1;i<=n;i++) a[i]=read(); q[0]=1; for(int i=1;i<=n;i++) q[i]=(long long)q[i-1]*a[i]%p; h[n+1]=1; for(int i=n;i>0;i--) h[i]=(long long)h[i+1]*a[i]%p; for(int i=n;i>0;i--) ans=(long long)(ans+(long long)q[i-1]*h[i+1]%p)*k%p; printf("%d",(long long)ans*power(q[n],p-2,p)%p); return 0; } 例题 \(3\) ： P1593 因子和 旁证：等比数列求和公式 式 \(1\)： \[S=\sum^{n}_{i=0}k^i \] 两边同时乘以 \(k\) 得式 \(2\) ： \[kS=\sum^{n+1}_{i=1}k^i \] 式 \(2\) 减去式 \(1\) 得： \[(k-1)S=k^{n+1}-1 \] 化系数为 \(1\) 得： \[S=\frac{k^{n+1}-1}{k-1}=\sum^{n}_{i=0}k^i \] 对于任意的 \(n=p_{1}^{k_{1}}\times p_{2}^{k_{2}}\times p_{3}^{k_{3}}\times ... \times p_{r}^{k_{r}}\)（其中 \(p_{1}^{k_{1}},p_{2}^{k_{2}},p_{3}^{k_{3}},...p_{r}^{k_{r}}\) 为 \(n\) 的不同素因子），则有因子和公式： \[\prod^{r}_{i=1}\sum^{k_i}_{j=0}{p_i}^j \] 观察可得内部的求和是一个等比数列，直接套用等比数列求和公式得： \[\prod^{r}_{i=1}\frac{{p_i}^{k_i+1}-1}{p_i-1} \] 可以在分解质因数的同时计算这个式子，同时用逆元处理分母部分。 注意，由于此题的模数 \(9901\) 很小，导致逆元可能不存在。当 \(9901\mid p_i-1\) 时，逆元不存在。但此时易得这个式子： \[\sum^{k_i}_{j=0}{p_i}^j\equiv\sum^{k_i}_{j=0}{1^j}\equiv k_i+1\pmod {9901} \] #include using namespace std; long long a,b,ans=1,mod=9901; long long power(long long c,long long p,long long m) { long long x=c,ans=1; while(p) { if(p%2==1)ans=ans*x%m; p/=2; x=x*x%m; } return ans; } long long mprime() { long long m=0,ans1=1; for(long long i=2;i<=a;i++) { if(a%i!=0)continue; m=0; while(a%i==0) { m++; a=a/i; } m*=b; if((i-1)%mod!=0)ans1=(power(i,m+1,mod)-1+mod)%mod*power(i-1,mod-2,mod)%mod; else ans1=(m+1)%mod; ans=ans*ans1%mod; } return 0; } int main() { scanf("%lld%lld",&a,&b); if(b==0||a==1){printf("1");return 0;} mprime(); printf("%lld",ans); return 0; } 后记 这篇笔记的数学公式又多又长又难懂，看来逆元难的根本不是其本身，而是综合时能否灵活运用。好像所有理科都是这样的