乘法逆元

存在线性同余方程\(ax\equiv 1\pmod b\),则称\(x\)为\(a\mod b\)的逆元，记作\(a^{-1}\)。逆元存在的意义就是在同余方程中作除法，正如所记作是\(a\)的倒数，所以再同余方程中除以\(a\)就是乘以\(a\)的逆元。(在作余数的运算中不能直接使用除法)

快速幂法

证明：

因为\(ax\equiv1\pmod b\),所以\(ax\equiv a^{b-1}\pmod b\)根据费马小定理，所以，\(x\equiv a^{b-2}\pmod b\)。

inline int qpow(int a,int b){
	int res=1;
	while(b){
		if(b&1)res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
int main(){
	inv=qpow(x,mod-2);//求x在模mod意义下的逆元
    return 0;
}

扩展欧拉定理

很显然\(ax\equiv 1\pmod b\)是一个线性同余方程，我们将它看作\(ax+by=1\)用扩展欧拉定理求解即可。

inline int exgcd(int a,int b,int &x,int &y){
	if(b==0){
		x=1;
		y=0;
		return a;
	}
	int d=exgcd(b,a%b,x,y);
	int t=x;
	x=y;
	y=t-(a/b)*y;
	return d;
}
int main(){
	gcd=exgcd(a,b,x,y);//exgcd的返回值是a,b的最大公约数
	inv=x;//x即为在模b意义下的逆元，y在这里仅作计算所用，在这里无意义
}

---

线性求逆元

连续的\(1...n\)的逆元

逆元可以当作同余方程中的倒数，我们也可以用这种性质求多个逆元。

首先，我们先求出\(s[i]=\prod_{j=1}^ij\),然后求出\(s[n]\)的逆元，然后逆推每一个\(i\)的逆元，\(sinv[i]\)为\(s[i]\)的逆元，\(sinv[i]=sinv[i+1]*(i+1)\)对于每个\(i\)的逆元\(inv[i]\),则\(inv[i]=s[i-1]\times sinv[i]\)。

【模板】乘法逆元

#include<bits/stdc++.h>
//#progma GCC optimize(2)
using namespace std;
#define int long long
const int MN=3e6+100;
int n,p;
int num[MN],ans[MN];
inline int exgcd(int a,int b,int &x,int &y){
	if(b==0){
		x=1,y=0;
		return a;
	}
	int d=exgcd(b,a%b,x,y);
	int t=x;
	x=y;
	y=t-(a/b)*y;
	return d;
}

signed main(){
	scanf("%lld%lld",&n,&p);
	num[0]=1;
	for(int i=1;i<=n;++i){
		num[i]=num[i-1]*i%p;
	}
	int svn,y;
	exgcd(num[n],p,svn,y);
	svn=(svn%p+p)%p;
	for(int i=n;i>=1;--i){
		ans[i]=(num[i-1]*svn)%p;
		svn=svn*i%p;
	}
	for(int i=1;i<=n;++i)printf("%lld\n",(ans[i]%p+p)%p);
	return 0;
}

求任意\(n\)个数的逆元

和上边的方法大同小异，首先也是算出前缀积\(s[i]\),求出前缀积的逆元\(sinv[i],sinv[i]=sinv[i+1]*a[i]\),通过前缀积的逆元来求每一个逆元\(inv[i],inv[i]=sinv[i]*s[i-1]\)。

例题：【模板】乘法逆元 2

这道题唯一需要再处理的就是\(k^i\),当然显然我们不可能每一次用快速幂来解决，再最后求逆元的循环中，一直让\(k\)乘以\(k\)即可,注意这道题读入特别多不加快读会T。

#include<bits/stdc++.h>
using namespace std;
const int MN=5e6+100;
#define int long long
int n,p,k,ans;
int s[MN],inv[MN],a[MN];
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^'0'),ch=getchar();
	return x*f;
}
inline int qpow(int a,int b){
	int res=1ll;
	while(b){
		if(b&1)res=res*a%p;
		a=a*a%p;
		b>>=1;
		
	}
	return (res%p+p)%p;
}

signed main(){
	n=read(),p=read(),k=read();
	s[0]=1,inv[n+1]=1;
	for(int i=1;i<=n;++i)a[i]=read(),s[i]=s[i-1]*a[i]%p;
	inv[n]=qpow(s[n],p-2);
	for(int i=n-1;i>=1;--i)inv[i]=inv[i+1]*a[i+1]%p;
	int cnt=k;
	for(int i=1;i<=n;++i){
		ans=(ans+((inv[i]*s[i-1])%p)*cnt)%p;
		cnt=(cnt*k)%p;
	}
	printf("%lld\n",(ans%p+p)%p);
	return 0;
}