#include <iostream>
using namespace std;
typedef long long ll;
ll a, b, c;
ll func(ll a, ll b) {
if (b == 1) {
return a % c;
}
if (b % 2 == 0) {
ll tmp = func(a, b / 2);
return (tmp * tmp) % c;
} else {
ll tmp1 = func(a, b / 2);
ll tmp2 = func(a, b / 2 + 1);
return (tmp1 * tmp2) % c;
}
}
int main() {
cin >> a >> b >> c;
cout << func(a, b) << endl;
}
대표적인 분할정복 문제이다. 재귀함수를 이용하여 거대한 제곱의 형태를 반씩 나누어 게산한다. 아무리 긴 제곱계산도 log2 만큼 줄일 수 있다.
long long을 사용할 때는 typedef를 사용해서 불필요한 타이핑을 줄이도록하자.