[수학] 분할정복을 이용한 거듭제곱

수학적 정의를 이용하여 거듭제곱을 하는 방법이다.

기존 거듭제곱의 경우, 모두 곱하기 때문에 O(N)의 시간이 걸리지만,

분할정복을 이용하면 O(LogN)에 결과 도출이 가능하다.

 

그냥 단순하게 2, 3등분하여 한방에 구한다는 뜻이다. 

재귀함수와 반복문 두 가지 방법으로 구현이 가능하다.

 

반복문의 경우 코드를 먼저 보자.

void powFunc(int a, int b) {
	int res = 1;
    
	while(b) {
		if (b % 2 != 0) {
			res *= a;
		}
		a *= a;
		b /= 2;
	}
	cout << res << "\n";
}

- 2, 3 등분으로 나누기 위해 b가 1이상일 동안 이루어진다.

- 만약 홀수인 경우, (위 식 그림에서) 마지막에 C가 추가적으로 곱해지기 때문에, 초기에 곱한다.

- 짝수의 경우, 마지막에 1이 될 때 최종 결과에 거듭제곱 결과를 곱한다.

 

관련 문제

1629번: 곱셈 (acmicpc.net)

18291번: 비요뜨의 징검다리 건너기 (acmicpc.net)