lp5431 【模板】乘法逆元2


挺套路的。
先计算出所有数的积的逆元,再计算除了这个数以外的数的积,然后乘一起,这样就完成了线性求逆元。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

typedef long long ll;
const int N=5000005;
inline int rd(){
	int rt=0;char ch=getchar();
	while(!isdigit(ch)){ch=getchar();}
	while(isdigit(ch)){rt=rt*10+ch-'0';ch=getchar();}
	return rt;
}
int n,MOD,k;
int a[N],pr[N],sf[N];
inline int pw(int A,int X){
	int RT=1;
	while(X){
		if(X&1){
			RT=1ll*RT*A%MOD;
		}
		A=1ll*A*A%MOD;X>>=1;
	}
	return RT;
}

void init(){
	scanf("%d%d%d",&n,&MOD,&k);
	int pl=1;
	pr[0]=sf[n+1]=1;
	for(int i=1;i<=n;++i){
		a[i]=rd();
	}
	for(int i=1;i<=n;++i){
		pr[i]=1ll*pr[i-1]*a[i]%MOD;
	}
	pl=pw(pr[n],MOD-2);
	for(int i=n;i>=1;--i){
		sf[i]=1ll*sf[i+1]*a[i]%MOD;
	}
	int nk=1;
	int ans=0;
	for(int i=1;i<=n;++i){
		nk=1ll*nk*k%MOD;
		ans+=1ll*(1ll*pr[i-1]*sf[i+1]%MOD)*(1ll*pl*nk%MOD)%MOD;ans%=MOD;
	}
	printf("%d\n",ans);
	
}
int main(){
	init();
	return 0;
}

“lp5431 【模板】乘法逆元2”的2个回复

  1. With havin so much content do you ever run into any issues of plagorism or copyright violation? My blog has
    a lot of unique content I’ve either created myself or outsourced but it appears a lot of it is popping it up all
    over the internet without my agreement. Do you know any methods to help prevent content from being ripped off?

    I’d really appreciate it.

    P.S. If you have a minute, would love your feedback on my
    new website re-design. You can find it by searching for “royal cbd” – no sweat
    if you can’t.

    Keep up the good work!

  2. I truly love your website.. Very nice colors & theme.
    Did you develop this website yourself? Please reply back as I’m trying to create my very own website and would like to find out where you got this from or just what
    the theme is called. Thanks!

    P.S. If you have a minute, would love your feedback on my new website
    re-design. You can find it by searching for «royal
    cbd» — no sweat if you can’t.

    Keep up the good work!

发表评论

电子邮件地址不会被公开。