谈资

Talk

928B BY knowing @ 2017-08-04 17:39:28 IN Problem 1759

#include<cstdio>
#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
const int N=1000100;

char b[N];

ll quick(ll a,ll n,ll c){
    a%=c;
    ll k=1;
    while(n){
        if(n&1)k=k*a%c;
        n>>=1;
        a=a*a%c;
    }
    return k;
}
ll phi(ll a){
    ll sum=a;
    for(int i=2;i*i<=a;i++){

        if(a%i==0){
                while(a%i==0)a/=i;
                sum=sum/i*(i-1);
        }

    }

    if(a>1)sum=sum/a*(a-1);
    return sum;
}
//ll a,c;
int main()
{
ll a,c;//这里会TLE,把这一行代码换到上二行就会AC,
    while(~scanf("%lld%s%lld",&a,b,&c)){
        ll ph=phi(c);

        ll k=0,cur=0;
        int len=strlen(b);

        for(int i=0;i<len;i++){
            k=k*10+b[i]-'0';
            if(k>ph){
                cur=1;k%=ph;
            }
        }

        ll ans=cur? quick(a,k+ph,c): quick(a,k,c);

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

    return 0;
}
Tips:本主题暂无回复。
登录OnlineJudge账号后可以发表和回复Talk~登录OnlineJudge
请点击右方按钮跳转至OnlineJudge登录页面。