34分且MLE

#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long
ll a,m;
string b;
ll big_mod(const string& s, ll mod) {
    ll res = 0;
    for (char c : s) {
        res = (res * 10 + (c - '0')) % mod;
    }
    return res;
}
bool str_less_than(const string& s, ll num) {
    string num_str = to_string(num);
    if (s.length() != num_str.length()) {
        return s.length() < num_str.length();
    }
    return s < num_str;
}
ll quick_pow(ll base, ll exp, ll mod) {
    ll res = 1 % mod;
    base %= mod;
    while (exp) {
        if (exp & 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return res;
}
int main(){
    cin>>a>>m>>b;
    vector<ll> phi(m+1);
    vector<ll> primes;
    vector<bool> isprime(m+1,false);
    phi[1]=1;
    for (ll i = 2; i <= m; i++) {
        if (!isprime[i]) {
            primes.push_back(i);
            phi[i] = i - 1;
        }
        for (ll j = 0; j < primes.size(); j++) {
            ll p=primes[j];
            if (i * p > m) break;
            isprime[i * p] = true;
            if (i % p == 0) {
                phi[i * p] = phi[i] * p;
                break;
            } 
            else {
                phi[i * p] = phi[i] * (p - 1);
            }
        }
    }
    ll phim=phi[m],gcd=__gcd(a,m);
    ll b1=0;
    if(gcd==1){
        b1=big_mod(b,phim);
    }else{
        if(gcd!=1&&str_less_than(b,phim)){
            b1=big_mod(b,phim);
        }else{
            b1=big_mod(b,phim)+phim;
        }
    }
    ll ans=quick_pow(a,b1,m);
    cout<<ans<<endl;
    return 0;
}