题目连接

题面：

题解：

代码：

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<ctime>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
ll mypow(ll a,ll b,ll p)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans;
}

ll only(ll n)
{
    ll ans=n;
    for(int i=2;i*i<=n;i++)
    {
        if(n%i) continue;
        ans=ans-ans/i;
        while(n%i==0) n/=i;
    }
    if(n>1) ans=ans-ans/n;
    return ans;
}

int main(void)
{
    ll a,m,ans=0;
    char ch;
    scanf("%lld%lld%*c",&a,&m);

    ll res=only(m);
    bool flag=false;
    while(isdigit(ch=getchar()))
    {
        ans=ans*10+ch-'0';
        if(ans>=res)
            ans%=res,flag=true;
    }
    if(flag) ans+=res;
    printf("%lld\n",mypow(a,ans,m));
    return 0;
}