BOJ 1629 : 곱셈

---

[BOJ 1629(S1) 리뷰]

 

쉬워보이지만 정답률이 낮은것엔 이유가 있다.

최대값이 21억이므로 21억을 곱하는 연산을 한다면 당연히 오버플로우가 생긴다.

이 문제는 재귀를 통해 해결해야한다.

 

x^16은 x^8 * x^2과 같음을 이용해야 한다.

---

 

#include <iostream>
#include <queue>
using namespace std;

long long int f(int A, int B, int C)
{
	if (B == 1) return A % C;
	long long int val = f(A, B / 2, C);
	val = val * val%C;
	if (B % 2 == 0) return val;
	return val * A%C;
}

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(0);
	int A, B, C;
	cin >> A >> B >> C;
	cout << f(A, B, C);
}