분할 정복을 이용한 최대공약수

01. 문제

 

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

1629번: 곱셈

 

02. 코드

 

#include <iostream>
using namespace std;

int a, b, c;

long long power(int n, int k) {
	if (k == 0) return 1;
	if (k == 1) return n;

	long long tmp = power(a, k / 2); 

	if (k % 2) {
		return ((tmp * tmp)%c * a) % c;
	}
	return (tmp * tmp) % c;
}

int main() {
	cin >> a >> b >> c;

	cout << power(a%c, b) << endl;
}

 

03. 풀이 전략

 

a와 b의 수가 큰 경우,

a^b를 구하는 방법은 다음과 같다.

 

power(a, b) = 1 (b가 0인 경우)

power(a, b) = a (b가 1인 경우)

power(a, b/2)^2 (b가 짝수인 경우)

power(a, b/2)^2*a (b가 홀수인 경우)

 

또한, 기회가 보이면 %c 를 바로 해줘야 하고, 큰 범위를 가지므로 long long 자료형을 사용해야 한다.