[백준] 1629 곱셈 / 분할 정복 (C++)

문제
자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

출력
첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

.
.
풀이

지수가 되는 수를 홀수인 경우, 짝수인 경우로 나눈다는 개념은 다른 사람들의 풀이에서 참고하였다.
그리고 모듈러 성질이라는 것을 알게되었다.
(ab)%c = (a%c b%c)%c

두 수의 곱을 c로 모드 연산을 할 경우,
각각의 수를 c로 모드 연산을 한 것의 곱을 c로 모드 연산한 값과 같다는 것

정수론에대해 공부를 조금 해봐야 할지도...

나는 기본적으로 Pow(n) 이 쪼개져나가는 방식을 그리며 코드로 작성하였다.
속도를 높이려고 메모이제이션도 구현했었는데, 입력값의 범위가 int전체라서 너무 커져서 오히려 메모리 초과가 났었다.

#include <iostream>
using namespace std;

long long A, B, C;

long long Pow(int b)
{
	if (b == 1)
	{
		return A % C;
	}
	
    // 홀수인 경우
	if (b % 2 == 1)
	{
		return (Pow(b / 2) * Pow(b / 2 + 1))%C;
	}
    // 짝수인 경우
	return (Pow(b / 2) * Pow(b / 2))%C;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);


	cin >> A >> B >> C;

	cout << Pow(B);

	return 0;
}