[1629] 곱셈

https://www.acmicpc.net/problem/1629

1629번: 곱셈

<문제>

분할정복을 이용한 거듭제곱을 구현하면 된다. 

 

X^N를 구하기 위해서는 X^(N/2)만 알고있으면 된다는 사실로부터 시간복잡도를 O(N)에서 O(logN)으로 줄일 수 있다. 

<소스코드>

#include<stdio.h>
int a,b,c;
long long pow(long long x, long long y) {
    long long num = 1;
 
    while (y > 0) {
        num %= c;
        x %= c;
        if (y % 2 == 1)
            num = (num*x)%c;
        x = (x*x)%c;
        y /= 2;
    }
    return num%c;
}
int main(void) {
    scanf("%d %d %d", &a, &b, &c);
    printf("%lld", pow(a,b)%c);
    return 0;
}