[1629] 곱셈

---

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

1629번: 곱셈

 

분할 정복 문제이다. 

거듭제곱을 분할정복으로 풀 수 있다는 것을 처음 알게 되었다!

 

제곱하는 횟수가 짝수라면 위의 식을, 홀수라면 아래식을 이용하면 된다.

세상에는 참 천재가 많은 듯 ,,

 

 

이렇게 한다고 끝이 아니고 숫자가 너무 커질 것을 대비하여 C로 나눈 나머지를 출력해야한다.

따라서 모든 계산 과정에다가 "%C"를 붙여주었다. 

그리고 범위를 생각하여 long long으로 잡았다. 안그러면 오류 난다!

#include <iostream>
using namespace std;

long long A, B, C;

// 분할정복 거듭제곱 알고리즘
long long dcsquare(long long a, long long b) {
	if (b == 1)return a % C;
	if (b % 2 == 0) {
		// even
		long long x = dcsquare(a, b / 2) % C;
		return (x * x) % C;
	}
	else {
		// odd
		long long x = dcsquare(a, (b - 1) / 2) % C;
		return ((x * x) % C * a) % C;
	}
}

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

	cin >> A >> B >> C;
	cout << dcsquare(A, B);
}