乘法逆元 线性递推阶乘求逆元、费马小定理、普适线性求逆元 欧拉定理结论

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rg register ll
#define inf 2147483647
#define lb(x) (x&(-x))
ll sz[200005],n;
template <typename T> inline void read(T& x)
{
    x=0;char ch=getchar();ll f=1;
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}x*=f;
}
inline ll query(ll x){ll res=0;while(x){res+=sz[x];x-=lb(x);}return res;}
inline void add(ll x,ll val){while(x<=n){sz[x]+=val;x+=lb(x);}}//第x个加上val
ll p,inv[5000005]={0,1};
int main()
{
	
	cin>>n>>p;
	cout<<1<<endl;
	for(rg i=2;i<=n;i++)
	{
		inv[i]=p-(p/i)*inv[p%i]%p;
		printf("%lld\n",inv[i]);
	}
    return 0;
    
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rg register ll
#define inf 2147483647
#define lb(x) (x&(-x))
template <typename T> inline void read(T& x)
{
    x=0;char ch=getchar();ll f=1;
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}x*=f;
}
ll a[5000005],sum,suf[5000005],n,p,k,pre;
inline ll qp(ll x,ll m)
{
	ll res=1;
	while(m)
	{
		if(m&1)res=res*x%p;
		x=x*x%p;
		m>>=1;
	}
	return res%p;
}
inline ll in(ll x)
{
	return qp(x,p-2);
}
int main()
{
	cin>>n>>p>>k;
	ll k1=k;
	pre=1,suf[n+1]=1;
	for(rg i=1;i<=n;i++)read(a[i]);
	for(rg i=n;i>=1;i--)suf[i]=suf[i+1]*a[i]%p;
	ll zong=in(suf[1]);
	for(rg i=1;i<=n;i++)sum+=zong%p*pre%p*suf[i+1]%p*k1,sum%=p,k1=k1*k%p,pre=pre*a[i]%p;
	cout<<sum<<endl;
    return 0;
    
}