P5431 乘法逆元 2
等式变换
取模后的被除数遇除法 变成 要乘逆元
没取之前，可以直接除再取模
#include<bits/stdc++.h>
using namespace std;
namespace{
template<typename T>
inline void read(T &s){
T f=1;s=0;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) f=-1;
for(;isdigit(ch);ch=getchar()) s=(s<<1)+(s<<3)+(ch^48);
}
}
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
int const N=5e6+7;
ll n,mod,k;
ll b[N],b2[N],a[N]; //kk[N]
inline int ksm(ll a,int b){
ll res=1;
while(b){
if(b&1) (res*=a)%=mod;
b >>= 1;
a*=a;
a%=mod;
}
return res;
}
int main(){
//fio;
//cin >> n >> mod >> k;
read(n);read(mod);read(k);
//kk[0]=1;
b[0]=1;
for(register int i=1;i<=n;++i){
//cin >> a[i];
read(a[i]);
//kk[i]=kk[i-1]*k%mod;
b[i]=b[i-1]*a[i]%mod;
}
b2[n+1]=1;ll ans=0,kk=1;
for(register int i=n;i>=1;--i){
b2[i]=b2[i+1]*a[i]%mod;
}
for(register int i=1;i<=n;++i){
(kk*=k)%=mod;
ans+=b[i-1]*b2[i+1]%mod *kk%mod;
ans%=mod;
}
ans*=ksm(b[n],mod-2);
cout << ans%mod ;
return 0;
}
