sdut 2605 A^X mod P

时间：2022-02-24 10:53:07

http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2605

这个题卡的是优化，直观解法是在求x^y时 用快速羃，但会TLE

快速羃其实就是把 y 变成了二进制 这样每求一次花费为 y 的二进制长度

我又把 y 变成了十进制进行求解 虽然优化了 但还是超时 优化的不够好，看了一下题解

我把 y 变成100000 进制 这样 y 的100000进制长度就变成了 2 只要事先打表，就可以快很多了 。

代码：

#include<iostream>

#include<cstdio>

#include<vector>

#include<stack>

#include<cstring>

#include<queue>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<string>

#include<set>

#include<map>

using namespace std;

const int INF=0x3f3f3f3f;

const long long MOD=1000000009;

const int M=100000;

const int N=1000005;

long long f[N];

long long c[N],d[N];

int main()

{

    //freopen("data.in","r",stdin);

    int T;

    scanf("%d",&T);

    for(int w=1;w<=T;++w)

    {

        printf("Case #%d: ",w);

        int n;

        long long A,K,a,b,m,P;

        //cin>>n>>A>>K>>a>>b>>m>>P;

        scanf("%d %lld %lld %lld %lld %lld %lld",&n,&A,&K,&a,&b,&m,&P);

        f[1]=K;

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

        f[i]=(a*f[i-1]+b)%m;

        c[0]=1;

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

        c[i]=c[i-1]*A%P;

        d[0]=1;

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

        d[i]=d[i-1]*c[M]%P;

        long long ans=0;

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

        {

            long long x=f[i]/M;

            long long y=f[i]%M;

            ans+=(d[x]*c[y])%P;

        }

        //cout<<(ans%P)<<endl;

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

    }

    return 0;

}

　　

相关文章