[백준 1629번] 곱셈 (C++)

/*************************************************
짝수번: A x A x A x A = (A x A) x (A x A)
홀수번: A x A x A x A x A = (A x A) x (A x A) x A
*************************************************/
#include<iostream>
using namespace std;

long long int dc(int a, int b, int c) {
	if (b == 1) return a % c;//base condition: A의 1승
	if (b % 2) return dc(a, b / 2, c) * dc(a, b / 2, c) % c * a % c;
	else return dc(a, b / 2, c) * dc(a, b / 2, c) % c;
}

int main(void) {
	cin.tie(0);
	ios_base::sync_with_stdio(NULL);
	int A, B, C;
	cin >> A >> B >> C;
	cout << dc(A, B, C);

	return 0;
}