[Silver 1] 1629번 곱셈

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

1629번: 곱셈

 

이 문제는 분할 정복을 이용한 거듭제곱을 사용해야 해결할 수 있다.

 

초기에는 이 알고리즘을 모른채 B번 제곱한 수를 구해 C로 나눈 나머지값을 출력하였다.

예제 값은 수가 작아 올바르게 출력되어 제출을 하였으나 틀리고 말았다.

 

분할 정복을 이용한 거듭제곱이라는 방법을 모른채 문제를 계속 시도하여 정답을 확인해 보았다.

 

분할 정복을 이용한 거듭제곱을 사용하면 C**n연산은 x를 n번 곱하므로 O(N)이지만, 이 방법을 사용하면 O(logN)에 거듭제곱 값을 구할 수 있다.

- n이 1이면 그냥 C의 1제곱이므로 return C를 해준다.

- n이 2이상일 때, C의 n제곱은 다음과 같다.

- 위 방식은 홀수인 경우와 짝수인 경우로 나눠지며 짝수인 경우 윗줄 식을 만족하고 홀수인 경우 아래 식을 만족한다.

 

위 식을 C++에서 제귀의 형식으로 구현할 수 있다.

- b가 1인 경우 return a%c를 하면 n이 1일 때를 만족할 수 있다.

- b를 계속해서 2로 나누어 divide 함수를 호출하면 언젠가 n이 1인 경우 값이 반환된다.

- 이후 n이 2 혹은 3인 경우의 값 ... n이 b인 경우의 값을 구할 수 있다.

 

 

 

#include <iostream>
using namespace std;
long long A, B, C;

long long divide(long long a, long long b, long long c) {
	if (b == 1) return a % c;

	long long calc = divide(a, b / 2, c) % c;
	if (b % 2 == 0) return calc * calc % c;
	else
		return calc * calc % c * a % c;
}

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

	

	cin >> A >> B >> C;

	cout << divide(A, B, C)<<'\n';
}