6) 백준 1629 - 곱셈

1629번: 곱셈 (acmicpc.net)

1629번: 곱셈

---

정말 고민을 많이 했던 문제.

처음 방식은 A를 곱한 수를 C로 나누었을 때 나머지를 이용했다.

하지만 시간 초과로 방법을 찾던 중 곱셈의 횟수를 줄이는 방법을 알았다.

#include <bits/stdc++.h>

using namespace std;


long long divide(long long A, long long B, long long C) {
	cout << "B : " << B << " ";
	if(B == 1) {
		return A%C;
	}
	long long tmp = divide(A, B/2, C) % C;
	cout << "tmp : " << tmp << endl;
	if(B % 2 == 0) {
		return tmp*tmp%C;
	}
	else {
		return tmp*tmp%C*A%C;
	}
}

int main(void) {
	long long A, B, C;
	cin >> A >> B >> C;
	
	cout << divide(A, B, C);
}

분할 정복을 이용하여 거듭제곱의 횟수를 줄일 수 있다.

이 내용은 따로 정리해야겠다.