분할정복을 이용한 거듭제곱(a^n 계산을 O(log n)으로)

Binary exponentiation(또는 Exponentiation by squaring)이라는 기법을 써주면 O(log n)의 시간복잡도로 a^n을 구할 수 있다. 분할정복을 이용한 거듭제곱이라고 부를 수 있다.

typedef long long ll;

ll binpow(ll a, ll b) {
	ll res = 1;

	while (b > 0) {
		if (b & 1)
			res *= a;

		a = a * a;
		b >>= 1;
	}

	return res;
}

반복문으로 짠 버전입니다. a(base)를 squaring을 하고, 동시에 b는 오른쪽 쉬프트를 해서 절반씩 줄여나간다. b&1일 때 해당 base를 곱해준다.

 

ll binpow_recur(ll a, ll b) {
	if (b == 0) return 1;

	ll res = binpow_recur(a, b/2);
	if (b & 1)
		return res * res * a;
	else
		return res * res;
}

재귀 버전.