模板 - n个数的乘法逆元

这道题里面不用保存 inva[i] ，而且还卡常。事实证明快读快到飞起，

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN=5000005;

int a[MAXN];

ll pp[MAXN];

inline int qpow(ll x,int n,int p){

    ll res=1;

    while(n){

        if(n&1){

            res=res*x;

            if(res>=p)

                res%=p;

        }

        x=x*x;

        if(x>=p)

            x%=p;

        n>>=1;

    }

    return res;

}

inline int read(){

    char c=getchar();

    int x=0;

    while(c<'0'||c>'9')

        c=getchar();

    while(c>='0'&&c<='9'){

        x=x*10+c-'0';

        c=getchar();

    }

    return x;

}

void solve(){

    int n=read(),p=read(),k=read();

    for(int i=1;i<=n;i++)

        a[i]=read();

    pp[0]=1;

    for(int i=1;i<=n;i++){

        pp[i]=pp[i-1]*a[i];

        if(pp[i]>=p)

            pp[i]%=p;

    }

    int invk=qpow(k,p-2,p);

    ll ans=0,ki=qpow(k,n,p);

    ll invpp=qpow(pp[n],p-2,p);

    for(int i=n;i>=1;i--){

        ll inva=invpp*pp[i-1];

        if(inva>=p)

            inva%=p;

        ans+=ki*inva;

        if(ans>=p)

            ans%=p;

        ki*=invk;

        if(ki>=p)

            ki%=p;

        invpp*=a[i];

        if(invpp>=p)

            invpp%=p;

    }

    printf("%lld\n",ans);

    return;

}

int main() {

#ifdef Yinku

freopen("Yinku.in","r",stdin);

#endif // Yinku

    solve();

    return 0;

}

巴特西

模板 - n个数的乘法逆元

最新文章

热门文章