알고리즘)(pow(A,B))mod C 를 logB 시간에 구하는 함수

#include <cstdio>
#include <algorithm>
 
typedef long long ll;
ll a,b,c;
 
ll mypow(ll a,ll b,ll c){
    ll ret = 1ll;
    while(b>0){
        if(b&1){
            ret = (ret* a) % c;
        }
        b /= 2;
        a  = (a*a) % c;
    }
    return ret;
}
 
int main(){
    freopen("input.txt","r",stdin);
    scanf("%lld %lld %lld",&a,&b,&c);
    printf("%lld",mypow(a,b,c));
}

간단하다.