题解 P5431 【【模板】乘法逆元2】

SSerxhs · 2019-05-31 13:50:57 · 题解

乘法逆元的一般形式，实际上做法比传统的线性做法更简单。

有两种做法。这里只放法一的代码，有不影响阅读的坑。

第一种做法：预处理前缀积数组 f[i]=\prod_{k=1}^ia_k，设前缀积逆元数组为 g[]，则可以得到 f[n] 的逆元 g[n]，由递推式 g[i]=g[i+1]*a[i+1] 求得所有 g[]，则 inv[a[i]]=f[i-1]*g[i]。

#include <stdio.h>
typedef long long ll;
const int N=5e6+2,M=5e6+2;
char c[M+2],*dd=c;
int a[N],b[N],s[N];
bool ed[N];
inline void read(register int &x)
{
    char *d=dd+1;
    while (((*d)<48)||((*d)>57)) ++d;
    x=*(d++)^48;
    while ((*d>=48)&&(*d<=57)) x=x*10+((*(d++))^48);
    dd=d;
}
inline int ksm(register int x,register int y,register int P)
{
    const int p=P;
    register int r=1;
    while (y)
    {
        if (y&1) r=(ll)r*x%p;
        x=(ll)x*x%p;
        y>>=1; 
    }
    return r;
}
int main()
{
    register int i,j,x,gs=0;
    c[fread(c+1,1,M,stdin)]=0;
    read(x);const int n=x;
    read(x);const int p=x;
    read(x);const int k=x;s[0]=1;
    for (i=1;i<=n;i++) { read(a[i]);s[i]=(ll)s[i-1]*a[i]%p; }
    i=n;b[n]=ksm(s[n],p-2,p);
    while (--i) b[i]=(ll)b[i+1]*a[i+1]%p;j=k;
    for (i=1;i<=n;i++,j=(ll)j*k%p) gs=(gs+(ll)j*s[i-1]%p*b[i])%p;printf("%d",gs);
}

第二种做法：预处理前缀积数组 f[] 和后缀积数组 g[] 和 inv[f[n]]=s，则 inv[a[i]]=f[i-1]*g[i+1]*s。