题解 | #纳米猫猫#

本题本意给了许多可以思考发展的点，总的来说有三种过法
由于模数较小，所以可以采用寻找循环节的方法
第一种过法：

#include <iostream>
#include <cstdio>
#include <set>
#include <list>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <string>
#include <sstream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <fstream>
#include <iomanip>
//#include <unordered_map>
using namespace std;
#define dbg(x) cerr << #x " = " << x << endl;
typedef pair<int, int> P;
typedef long long ll;
#define FIN freopen("in.txt", "r", stdin);freopen("out.txt","w",stdout);

ll getmod(string num, int mod)
{
    ll ret = 0;
    ll n = num.size();
    for(int i = 0; i < n; i++)
    {
        ret = ret * 10 + num[i] - '0';
        ret %= mod;
    }
    return ret;
}

vector<ll> v;

ll vis[1005];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string n;
    ll x, mod;
    cin >> x >> n >> mod;
    if(n=="1")return !printf("%d",1%mod);
    if(x==0)return !printf("0");
    memset(vis, -1, sizeof(vis));
    vis[1] = 0;
    v.push_back(1);
    int cur = 0;
    int looplen = 0;
    while(1)
    {
        if(n.size() < 9 && cur + 1 >= atoi(n.c_str()))
        {
            cout << v[cur] << endl;
            return 0;
        }
        ll num = v[cur] * x % mod;
        if(vis[num] != -1)
        {
            looplen = vis[num];
            break;
        } 
        else
        {
            vis[num] = ++cur;
            v.push_back(num);
        }
    }

    int nn = v.size();
    int nonloop = looplen;
    looplen = nn - looplen;
    int pos = (getmod(n, looplen) - nonloop + looplen) % looplen;
    pos = (pos - 1 + looplen) % looplen;
    pos = pos + nonloop;
    cout << v[pos] << endl;

    return 0;
}

第二种过法：十进制快速幂

#include<iostream>
using namespace std;
typedef long long ll;
ll x,mod;
string s;
ll pow(){
    ll ans=1%mod,ss=x;
    int str[100010]={0};
    str[s.length()-1]-=1;
    for(int i=s.length()-1;~i;i--){
        str[i]+=s[i]-'0';
        if(i){
            str[i-1]-=1;
            str[i]+=10;
            str[i-1]+=str[i]/10;
            str[i]%=10;
        }
        ll cnt=str[i],cur=ss;
        for(int j=1;j<=cnt;j++)
            ans=ans*ss%mod;
        for(int j=1;j<10;j++)
            cur=cur*ss%mod;
        ss=cur;
    }
    return ans;
}
int main(){
    cin>>x>>s>>mod;
    cout<<pow();
}

第三种过法：快速幂+大数取余+欧拉降幂

#include<iostream>
using namespace std;
typedef long long ll;
bool flag=false;
ll read(string s,ll mod){
    ll x=0;
    for(int i=0;i<s.length();i++){
        x=((x<<3)+(x<<1)+(s[i]^48));
        if(x>=mod)flag=true,x%=mod;
    }
    return (x+mod-1)%mod;
}
ll pow(ll s,ll n,ll mod){
    ll sum=1;
    while(n){
        if(n&1)sum=sum*s%mod;
        s=s*s%mod;
        n>>=1;
    }
    return sum;
}
ll phi(ll x){
    ll t=x;
    for(int i=2;i<=x/i;i++)
        if(x%i==0){
            while(x%i==0)x/=i;
            t=t*(i-1)/i;
        }
    if(x>1)t=t*(x-1)/x;
    return t;
}
int main(){    
    ll x,mod,n;
    string nn;
    cin>>x>>nn>>mod;
    if(x==0){
        if(nn=="1")cout<<1%mod;
        else cout<<"0";
        return 0;
    }
    n=read(nn,phi(mod));
    if(flag) cout<<pow(x%mod,n%phi(mod)+phi(mod),mod);
    else cout<<pow(x%mod,n,mod);
}  

附带一个python3奇妙代码（python大数的神！）

x,n,mod=map(int,input().split(" "))
print(pow(x,n-1,mod))