[洛谷 5431,loj 161]乘法逆元 2

题目链接

https://www.luogu.org/problem/P5431

https://loj.ac/problem/161

题解

一个线性求给定数列每个数的逆元的黑科技。

我们求出序列前缀积 \(s_i\)，并求出 \(s_n\) 的逆元 \(sv_n\)。

根据下面这个式子，我们可以求出前缀积逆元 \(sv_{n-1} , \ldots , sv_1\)。

$$sv_n \times a_n \equiv sv_{n-1} \times a_n \times a_n^{-1} \equiv sv_{n-1} \pmod p$$

由 \(a_i^{-1} \equiv s_{i-1} \times sv_i \pmod p\)，我们就可以求出 \(a_1^{-1} , \ldots , a_n^{-1}\)。

整个过程我们只执行了一次快速幂求逆元的操作，时间复杂度 \(O(n+ \log p)\)。

#include <cstdio>
int a[5000005],n,p,k;
long long s[5000005],sv[5000005];
int read()
{
 int res=0;
 char c=getchar();
 while(c<'0'||c>'9')
  c=getchar();
 while(c>='0'&&c<='9')
 {
  res=res*10+c-'0';
  c=getchar();
 }
 return res;
}
long long fpow(long long x,long long y)
{
 long long ans=1;
 while(y)
 {
  if(y&1)ans=ans*x%p;
  x=x*x%p;
  y>>=1;
 }
 return ans;
}
int main()
{
 n=read(),p=read(),k=read();
 s[0]=1;
 for(int i=1;i<=n;i++)
 {
  a[i]=read();
  s[i]=s[i-1]*a[i]%p;
 }
 sv[n]=fpow(s[n],p-2);
 for(int i=n;i;i--)
  sv[i-1]=sv[i]*a[i]%p;
 long long sk=1,ans=0;
 for(int i=1;i<=n;i++)
 {
  long long inv=sv[i]*s[i-1]%p;
  sk=sk*k%p;
  ans=(ans+sk*inv)%p;
 }
 printf("%d\n",int(ans));
 return 0;
}