【分治】快速模幂

#include <iostream>
#include <cstdio>

using namespace std;

//a*b % n = (a % n)*(b % n) % n
long long int mo(long long int x,long long int n,long long int a){
    if(x==a){
        return 0;
    }
    if(n==1){
        return x%a;
    }
    if(n==2){
        return x*x%a;
    }
    if(n==3){
        return x*x*x%a;
    }
    if(n==4){
        return x*x*x*x%a;
    }
    if(n%2==0){
        return mo(x,n/2,a)*mo(x,n/2,a)%a;
    }
    if(n%2!=0){
        return mo(x,(n-1)/2,a)*mo(x,(n-1)/2,a)*x%a;
    }
}

int main()
{
    int x;
    int n;
    int a;
    long long int jieguo;
    while(scanf("%d %d %d",&x,&n,&a)!=EOF){
        jieguo=mo(x,n,a);
        printf("%lld\n",jieguo);
    }
    return 0;
}