x^n 을 O(log n)에 구하기

$x^n$을 단순히 for문으로 구한다고 하면 $O(n)$만큼의 시간이 걸립니다.

이를 분할정복을 이용해서 빠르게 구할 수 있습니다.

 

$2^{100}$을 구한다고 해보겠습니다.

 

$2^{100} = 2^{50} * 2^{50}$입니다. 그럼 $2^{50}$을 구한다면 그 수를 제곱해서 $2^{100}$을 구할 수 있습니다.

마찬가지로 $2^{50} = 2^{25} * 2^{25}$입니다. 그럼 $2^{25}$을 구한다면 그 수를 제곱해서 $2^{50}$을 구할 수 있습니다.

$2^{25}$는 2로 나누어지지 않습니다. 이런 경우에는 $2^{12}*2^{12}*2$를 이용하면 됩니다.

 

이런 식으로 진행하면 $O(log n)$에 구할 수 있습니다.

 

보통 이런 종류의 문제는 $x^n$을 $m$으로 나눈 나머지를 구하는 경우가 많습니다. $xy\,\bmod\,m = x\,\bmod\,m  * y\,\bmod\,m $이므로 각 연산마다 $m$으로 나눈 나머지를 취해주면 됩니다.

 

#include<iostream>
using namespace std;
int pow(int n, int p, int m) {
	if (p == 0) return 1;
	if (p == 1) return n;
	int tmp = pow(n, p / 2, m);
	if (p % 2 == 0) return tmp * tmp % m;
	else return tmp * tmp % m * n % m;
}
int main() {
	int n, p, m;
	cin >> n >> p >> m;
	printf("%d", pow(n, p, m));
	return 0;
}