CodeUp[Q_2640] : n의 k승 구하기 2

1. 문제

https://codeup.kr/problem.php?id=2640

n의 k승 구하기 2

[출처 : 코드업(https://codeup.kr/)]

이번에는 n과 k가 주어지면 n^k의 값을 1,000,000,007로 나눈 나머지를 구하는 문제입니다.

1<=n<=100,000 이고 1<=k<=100,000,000이기때문에 n^k의 값은 계산을 하지 못할정도 큰수가 나오게됩니다.

또한 k의 값도 매우 큰수이기 떄문에 n의 k번 곱하면 시간초과가 나옵니다.

그래서 이번문제는 분할정복 알고리즘을 이용하여 계산해야 됩니다.

 

---

분할 정복

n^k = (n^(k/2))^2을 이용하여 풀어주어야 합니다.

2^10 = (2^5)^2 = (2 * (2^2)^2)^2 = ((2 * ((2^1)^2)^2)^2

 

 

2. 풀이방법

STEP 1. k를 2로 나누웠을때 나머지가 있는지 없는지 확인

STEP 2. 나머지가 있으면 n^2 * n, 없으면 n^2을 1,000,000,007로 나누워 준다.

 

 

3. 해답

#include <stdio.h>

void main() {
	long long int n, tmp;
	int k;

	int Arr[40] = { 0, };
	int p = 0;

	scanf("%lld %d", &n, &k);

	while (k != 1) {
		if (k % 2 == 0) Arr[p++] = 1; // 짝수
		else if (k % 2 == 1) Arr[p++] = -1; // 홀수
		k /= 2;
	}
	tmp = n;
	for (int i = p - 1; i >= 0; i--) {
		if (Arr[i] == 1) { // 짝수
			tmp = tmp * tmp;
			tmp %= 1000000007;
		}
		else if (Arr[i] == -1) { // 홀수
			tmp = tmp * tmp;
			tmp %= 1000000007;

			tmp *= n;
			tmp %= 1000000007;
		}
	}

	printf("%lld", tmp);
}