거듭제곱

거듭제곱

기본 거듭제곱

• 음이 아닌 정수 a, x와 자연수 m에 대해 a^x(mod m)  ← 모듈러 취하는 이유: integer overflow 때문!
• 거듭 제곱 정의대로 a를 x번 곱하면 된다.
• 시간 복잡도: O(x)

 

분할정복을 이용한 거듭제곱 (더 빠른 방법)

• x가 짝수일 때 a^x = a^(x/2) * a^(x/2) 로 구하기
• x가 홀수일 때 a^x = a^(x/2) * a^(x/2) * a 로 구하기
• 시간 복잡도: O(logx)

---

C++로 구현

• 반복문

int m;
int fpow2(int a, int x) {
	int ret = 1;
	while (x) {
		if (x % 2) ret = ret * a % m;
		a = a * a % m;
		x /= 2;
	}
	return ret;
}

 

• 재귀문

int m;
int fpow1(int a, int x) {
	if (x == 0) return 1;
	int ret = fpow1(a, x / 2);
	ret = ret * ret % m;
	if (x % 2) ret = ret * a % m;
	return ret;
}