问题标题: 酷町堂：关于一道题的辛酸血泪史

首次看到2942这道题，la ji的我直接写出以下WA0代码

#include<iostream>
#include<cmath>
using namespace std;
int main(){
    long long b,p,k,n;
    cin>>b>>p>>k;
    n=pow(p,b);
    cout<<b<<"^"<<p<<" mod "<<k<<"="<<n%k;
    return 0;
}

之后，我悟了，5分题绝不会这么简单，深知数据范围之大，于是la ji的我又码出以下TLE10分的代码

#include<iostream>
using namespace std;
int main(){
    long long b,p,k;
    cin>>b>>p>>k;
    long long a=b%k,sum=1;
    for(int i=1;i<=p;i++){
        sum=(sum*a)%k;
    }
    cout<<b<<"^"<<p<<" mod "<<k<<"="<<sum;
    return 0;
}

之后，我又悟了，可以用余数周期性写，于是RE10分的代码又出现了

#include<iostream>
using namespace std;
long long c[100005];
int main(){
    long long b,p,k,n,pos;
    cin>>b>>p>>k;
    long long a=b%k,sum=1,cnt=0;
    for(int i=1;i<=p;i++){
        sum=(sum*a)%k;
        c[++cnt]=sum;
        if(sum==1){
            pos=i;
            break;
        }
    }
    cout<<b<<"^"<<p<<" mod "<<k<<"="<<c[p%pos];
    return 0;
}

数组开小空悲切，于是RE+TLE30分的代码又双叒叕出现了。。。

#include<iostream>
using namespace std;
int c[50000005],cnt;
long long b,p,k,ans,sum=1,a;
int main(){
    cin>>b>>p>>k;
    a=b%k;
    for(int i=1;i<=p;i++){
        sum=(sum*a)%k;
        c[++cnt]=sum;
        if(sum==1){
            ans=c[p%i];
            break;
        }
    }
    cout<<b<<"^"<<p<<" mod "<<k<<"="<<ans;
    return 0;
}

因为TLE的点有点卡边，于是加了个O3，然后50分了 。。。

#include<iostream>
#pragma GCC optimize(3)
using namespace std;
int c[50000005],cnt;
int main(){
    long long b,p,k,n,pos;
    cin>>b>>p>>k;
    long long a=b%k,sum=1;
    for(int i=1;i<=p;i++){
        sum=(sum*a)%k;
        c[++cnt]=sum;
        if(sum==1){
            pos=i;
            break;
        }
    }
    cout<<b<<"^"<<p<<" mod "<<k<<"="<<c[p%pos];
    return 0;
}

最后想到有可能一直卡在余数为5或6，改之后还是RE50分wtcl

#include<iostream>
#pragma GCC optimize(3)
using namespace std;
int c[50000005],cnt;
long long b,p,k,ans,sum=1,a;
int main(){
    cin>>b>>p>>k;
    a=b%k;
    for(int i=1;i<=p;i++){
        sum=(sum*a)%k;
        c[++cnt]=sum;
        if(c[i]==5&&c[i-1]==5) {ans=5;break;}
        if(c[i]==6&&c[i-1]==6) {ans=6;break;}
        if(sum==1)             {ans=c[p%i];break;}
    }
    cout<<b<<"^"<<p<<" mod "<<k<<"="<<ans;
    return 0;
}

所以说到底我还是来求助的QWQ