[백준] 1629 곱셈

[백준] 1629 곱셈

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

#include <iostream>
using namespace std;

typedef long long ll;

ll a, b, c;

ll calc(int n) {
	if (n == 0) return 1;
	if (n == 1) return a % c;
	
	ll res;
	if (n % 2 == 0) {
		res = calc(n / 2) * calc(n / 2);
		res %= c;
	}
	else {
		res = calc((n - 1) / 2) * calc((n - 1) / 2);
		res %= c;
		res *= a;
		res %= c;
	}
    
	return res;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> a >> b >> c;

	cout << calc(b);

	return 0;
}