P5431 【模板】乘法逆元2

P5431 【模板】乘法逆元2

题意：

Solution：

这题主要是学一个想法。
$$\begin{gathered} s_i=a_1\ast a_2\ast ...\ast a_i \\ \frac{1}{s_i}=\frac{1}{a_1\ast a_2\ast ...\ast a_i} \\ \frac{1}{s_{i-1}}=\frac{1}{s_i}\ast a_i \\ \frac{1}{a_i}=\frac{s_{i-1}}{s_i} \end{gathered}$$
因此对于此题，只要先求出$s_n^{-1}$，然后逆推出$s_i^{-1}$，和对应$a_i^{-1}$

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
char ch;
void read(int &x){
   
	x=0;
	for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';ch=getchar())
		x=(x<<3)+(x<<1)+(ch&15);
}
int n,p,k;
int a[5000005];
int ext_gcd(int a,int b,int &x,int &y)
{
   
    if(b==0)
    {
   
        x=1;y=0;
        return a;
    }
    int d=ext_gcd(b,a%b,x,y);
    int tem=y;
    y=x-a/b*y;
    x=tem;
    return d;
}
int inv(int a,int b)
{
   
    int x,y;
    int d=ext_gcd(a,b,x,y);
    x=(x%p+p)%p;
    return x;
}
int Inv[5000005],b[5000005];
int main()
{
   
    read(n);read(p);read(k);
    int qaq=1;
    for(int i=0;i<n;i++)
    {
   
        read(a[i]);
        if(i==0)b[i]=a[i];
        else b[i]=1ll*b[i-1]*a[i]%p;
    }
    qaq=inv(b[n-1],p);
    for(int i=n-1;i>=0;i--)
    {
   
        if(i==0){
   Inv[i]=qaq;break;}
        Inv[i]=1ll*qaq*b[i-1]%p;
        qaq=1ll*qaq*a[i]%p;
    }
    int res=0;
    int q=1;
    for(int i=0;i<n;i++)
    {
   
        q=1ll*q*k%p;
        res=1ll*(res+1ll*Inv[i]*q%p)%p;
    }
    printf("%d",res);
    return 0;
}