[C++] 백준 1629번 곱셈

분할정복 문제입니다.

(A^B) % C를 출력하면 됩니다.
B를 전부 하나하나 곱하면은 시간초과가 날 수 있습니다.

2^4의 경우
4^2와 동일합니다.

2^8의 경우
4^4
16^2와 동일합니다.

이처럼 2로 나누어 떨어질 경우 그 수로 곱한 후
승수를 2로 나눈 만큼 제곱하면 됩니다.

#include <iostream>
using namespace std;

int A, B, C;

int divCon(int n, int k) {
	int result;
	int x;

	if (k == 0) {
		return 1;
	}

	x = divCon(n, k / 2);
	result = 1LL * x * x % C;

	if (k % 2) {
		result = 1LL * result * n % C;
	}

	return result;
}

int main(int argc, char *argv[]) 
{
	cin >> A;
	cin >> B;
	cin >> C;

	cout << divCon(A, B) << endl;
}