문제 개요
양의 정수 a와 매우 큰 양의 정수 b가 배열 형태로 주어졌을 때, a^b mod 1337의 값을 계산하는 것이 목표입니다. 예를 들어 a = 2이고 b = [1,0](즉, 숫자 10)이라면 결과는 1024입니다.
b가 일반적인 정수 자료형의 범위를 훨씬 넘어설 수 있기 때문에, 지수를 한 번에 다루는 대신 자릿수 단위로 분할하여 처리하는 전략이 필요합니다.
풀이 접근 방법
핵심 아이디어는 두 가지입니다.
- 빠른 거듭제곱(모듈러 지수 연산): 반복 곱셈 대신 제곱으로 분할하여 O(log n) 시간 안에 거듭제곱을 계산합니다.
- 재귀적 분할: b = [d1, d2, ..., dk]라면 a^b = ((a^(b/10))^10) × (a^dk) 형태로 분해할 수 있습니다.
구체적인 알고리즘은 다음과 같습니다.
- base와 power를 인자로 받는 powerMod() 메서드를 정의합니다.
- m := 1337, ret := 1로 초기화합니다.
- power가 0이 아닌 동안 다음을 반복합니다.
- power가 홀수이면 ret := ret × base mod m
- base := base² mod m
- power := power / 2
- ret을 반환합니다.
- a와 b를 인자로 받는 superPow() 메서드를 정의합니다.
- b의 크기가 0이면 1을 반환합니다(재귀 종료 조건).
- last := b의 마지막 원소로 설정한 뒤, b에서 마지막 원소를 제거합니다.
- (powerMod(superPow(a, b), 10) × powerMod(a, last)) mod 1337을 반환합니다.
C++ 구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int powerMod(lli base, lli power){
lli mod = 1337;
lli ret = 1;
while(power){
if(power & 1) ret = (ret * base) % mod;
base = (base * base) % mod;
power >>= 1;
}
return ret;
}
int superPow(int a, vector<int>& b) {
if(b.size() == 0) return 1;
int last = b.back();
b.pop_back();
return (powerMod(superPow(a, b), 10) * powerMod(a, last)) % 1337;
}
};
main(){
Solution ob;
vector<int> v = {1,0};
cout << (ob.superPow(2, v));
}입력
2 [1,0]
출력
1024
동작 원리 살펴보기
예제에서 b = [1,0]은 숫자 10을 의미합니다. superPow는 재귀적으로 호출되며 지수의 마지막 자릿수부터 하나씩 처리합니다. 각 단계에서 이미 계산된 하위 지수의 결과에 10제곱을 적용한 뒤, 마지막 자릿수만큼 추가로 곱하는 방식으로 진행됩니다. 이렇게 하면 중간 결과가 커지기 전에 항상 mod 1337을 적용하므로 오버플로 없이 안전하게 답을 구할 수 있습니다.