[C/C++] 백준 - 13171번 : A

https://www.acmicpc.net/problem/13171

13171번: A

문제

음이 아닌 두 정수 A, X 가 있을 때 AX을 구하는 방법을 생각해보자. 물론 이 수는 매우 클 수 있기에, 1,000,000,007 (= 109 + 7)로 나눈 나머지를 구할 것이다. a mod x를 a를 x로 나눴을 때의 나머지라고 표현하면,

(a × b) mod x = {(a mod x) × (b mod x)} mod x

가 성립하기 때문에, 어떤 두 정수를 1,000,000,007로 나눈 나머지만 알고 있어도 그 두 정수의 곱을 1,000,000,007로 나눈 나머지를 쉽게 계산할 수 있다.

본 문제로 돌아가서, 그렇다면 이제 A를 X 번 곱하면 AX을 쉽게 구할 수 있을 것 같아 보인다. 그러나 안타깝게도 X가 상당히 커서 64비트 정수의 범위에 있다면 A를 하나하나씩 곱하는 방식으로는 상상할 수 없을 정도로 긴 시간이 흘러야 답을 찾을 수 있을 것이다. 그래서 다음과 같이 곱셈의 횟수를 줄이는 방법을 사용한다.

1. 먼저 A1, A2, A4, A8, ...을 순서대로 계산한다. 각 수는 이전에 있는 수를 제곱함으로써 계산할 수 있고, 지수가 X 를 딱 넘지 않을 시점까지만 계산하면 충분할 것이다. X가 64비트 정수의 범위에 있으므로 계산하는 수는 64개보다 작을 것이다.
2. 이제 X 를 이진수로 나타내 보자. 예를 들어 X를 11로 두면, X = 11 = 1 + 2 + 8이다. 그런데 지수법칙에 의해, A11 = A1+2+8 = A1 × A2 × A8이 성립한다. 이를 통해 1번 단계에서 미리 계산해 놓았던 수 몇 개만 곱해서 AX 을 계산할 수 있음을 알 수 있다.

즉, 차례로 A를 곱해 나간다면 시간이 X에 비례하게 걸리겠지만, 위의 방법을 이용하면 시간이 log(X)에 비례하게 걸리게 된다. AX를 구하는 프로그램을 작성하라.

 

---

A의 X승을 계산해야 할 때 O(N)으로 하나 하나 다 계산하는 방법이 아닌 분할 정복을 이용하여 O(logN)으로 해결해야하는 문제이다. 

O(logN)으로 해결하기 위해서는 100승을 계산할 때 1승부터 100승까지 쭉 이어 나가는 방식이 아니라

100승을 50승 * 50승으로 나누고 이것을 또 25승 * 25승 * 25승 * 25승 이런식으로 분할하여 나누어 구한 후 계산하는 방법이다. 만약 지수가 짝수일 경우에는 이처럼 계속 분할하면 되고 지수가 짝수일 경우에는 계산하기 쉽도록 짝수의 형태가 되도록 바꿔줘야한다.

 

예를 들어 11승은 홀수이므로 짝수로 바꿔줘야하고 이는 1승 * 10승 이렇게 바꿔줄 수 있다. 그럼 10승은 다시 짝수가 되므로 위 방식대로 계산해주면 된다.

 

이를 코드로 그대로 구현하였으니 코드를 통해 충분히 이해할 수도 있다.

#include <iostream>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

using namespace std;

ll A, X;

void input() {
	cin >> A >> X;
}

ll power(ll op, ll exp) {
	if (exp == 1) return op;
	if (exp % 2 != 0) {
		return (op * power(op, exp - 1)) % Mod;
	}
	return (power(op, exp / 2) * power(op, exp / 2)) % Mod;
}

ll solution() {
    A %= Mod;
	return power(A, X) % Mod;
}

int main() {
	fastio;
	input();
	cout << solution() << endl;

	return 0;
}