計蒜客 簡單的快速幂

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn=1000000+100;
const int prinum=100000+100;

int prime[prinum],tot;
bool isprime[prinum];

char B[maxn];
LL A,C;

void init(){
  
  for(int i=0;i<prinum;i++) isprime[i]=true;
  isprime[0]=isprime[1]=false;
  tot=0;
  for(int i=2;i<prinum;i++){
    
    if(isprime[i]) prime[tot++]=i;
    for(int j=0;j<tot && i*prime[j]<prinum;j++){
      
      isprime[i*prime[j]]=false;
      if(!(i%prime[j])) break;
    }
  }
}

LL mypow(LL a,LL b,LL c){
  
  LL sum=1;
  while(b){
    
    if(b&1) sum=sum*a%c;
    a=a*a%c;
    b>>=1;
  }
  return sum;
}

int main(){
  
  init();
  while(scanf("%lld %s %lld",&A,B,&C)==3){
    
    LL newC=C;
    LL phiC=C;
    for(int i=0;i<tot;i++){
      
      if(1LL*prime[i]*prime[i]>C) break;
      if(C%prime[i]==0){
        
        while(C%prime[i]==0) C/=prime[i];
        phiC=phiC/prime[i]*(prime[i]-1);
      }
    }
    if(C!=1) phiC=phiC/C*(C-1);
    
    int len=strlen(B);
    LL tmpB=0;
    for(int i=0;i<len;i++) tmpB=(tmpB*10+B[i]-'0')%phiC;
    printf("%lld\n",mypow(A,tmpB+phiC,newC));
  }
}