문제

음이 아닌 두 정수 A, X 가 있을 때 AX을 구하는 방법을 생각해보자. 물론 이 수는 매우 클 수 있기에, $1,000,000,007 (= 10^9 + 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$ 번 곱하면 $A^X$ 을 쉽게 구할 수 있을 것 같아 보인다. 그러나 안타깝게도 $X$ 가 상당히 커서 64비트 정수의 범위에 있다면 $A$ 를 하나하나씩 곱하는 방식으로는 상상할 수 없을 정도로 긴 시간이 흘러야 답을 찾을 수 있을 것이다. 그래서 다음과 같이 곱셈의 횟수를 줄이는 방법을 사용한다.

먼저 $A^1$, $A^2$, $A^4$, $A^8$, $\cdots$ 을 순서대로 계산한다. 각 수는 이전에 있는 수를 제곱함으로써 계산할 수 있고, 지수가 $X$ 를 딱 넘지 않을 시점까지만 계산하면 충분할 것이다. $X$ 가 64비트 정수의 범위에 있으므로 계산하는 수는 64개보다 작을 것이다. 이제 $X$ 를 이진수로 나타내 보자. 예를 들어 $X$ 를 11로 두면, $X = 11 = 1 + 2 + 8$ 이다. 그런데 지수법칙에 의해, $A^{11} = A^{1+2+8} = A^1 × A^2 × A^8$ 이 성립한다. 이를 통해 1번 단계에서 미리 계산해 놓았던 수 몇 개만 곱해서 $A^X$ 을 계산할 수 있음을 알 수 있다. 즉, 차례로 $A$ 를 곱해 나간다면 시간이 $X$ 에 비례하게 걸리겠지만, 위의 방법을 이용하면 시간이 $log(X)$ 에 비례하게 걸리게 된다. $A^X$ 를 구하는 프로그램을 작성하라.

입력

• 첫 번째 줄에는 정수 $A(1 ≤ A ≤ 10^{18})$ 이 주어진다.
• 두 번째 줄에는 정수 $X(1 ≤ X ≤ 10^{18})$ 가 주어진다.

출력

• $A^X$ 을 출력한다. 이 수는 매우 커질 수 있으므로 $1,000,000,007$ 로 나눈 나머지를 출력해야 한다.

---

1. 해결방법 및 소스코드

• 문제의 설명 그대로 코드를 짜면 된다.

#include <iostream> int MAX_LENGTH = 100; int main() { //result: 최종결과 //start: 최종결과를 구하기 위해 필요한 인덱스 long long A, X, C; C = 1000000007; long long result = 1; long long start; scanf("%lld %lld", &A, &X); //toBinary: B를 이진수로 바꿔 저장한다. //binIndex: toBinary에서 사용할 인덱스 변수 int toBinary[MAX_LENGTH] = { 0, }; int binIndex = 0; //ingredients: 답을 구하기 위한 계산의 재료들이 저장됨. //재료들이란, A%C, (A^2)%C, (A^4)%C, (A^8)%C 등을 일컫는다. //temp: 재료들을 만들 임시 변수 long long ingredients[MAX_LENGTH]; long long temp = A % C; ingredients[0] = temp; //X를 이진수로 바꿔 저장하는 작업 while (X > 0) { toBinary[binIndex] = X % 2; binIndex++; X /= 2; } //재료들을 필요한만큼(binIndex만큼) 계산하여 준비해두는 과정 for (int i = 1; i < binIndex; i++) { ingredients[i] = (ingredients[i - 1] * ingredients[i - 1]) % C; } //toBinary에서 처음 1이 나온 칸에 대응하는 수를 result에 저장 //최종 결과를 구하기 위해 start에 binIndex를 탐색할 인덱스를 저장 for (int i = 0; i < binIndex; i++) { if (toBinary[i]) { result = ingredients[i]; start = i + 1; break; } } //toBinary에서 1이 나올때마다 result를 업데이트 for (int i = start; i < binIndex; i++) { if (toBinary[i]) { result = (result * ingredients[i]) % C; } } printf("%d\n", result); }