문제 개요
이 문제에서는 네 개의 값 A, B, C와 소수 M이 주어지며, 우리가 구해야 할 것은 소수를 법으로 하는 거듭제곱의 거듭제곱 값입니다.
즉, (A ^ (B ^ C)) (mod M)의 값을 계산하는 것이 목표입니다.
예시를 통해 문제를 살펴보겠습니다.
입력
A = 3, B = 6, C = 2, M = 11
출력
3
설명
(A ^ (B ^ C)) = (3 ^ (6 ^ 2)) = (3 ^ 36) (mod 11) = 3
풀이 접근 방법
가장 단순한 해결 방법은 (A ^ (B ^ C))를 직접 계산하는 것입니다. 먼저 (B^C)의 값을 구한 뒤, 다시 (A ^ (B ^ C))를 계산하고 마지막으로 M에 대한 나머지를 취하면 됩니다. 하지만 (B^C)는 지수가 겹치기 때문에 매우 큰 수가 되어 저장 자체가 어려울 수 있으며, 계산 과정에서 오버플로우가 발생할 위험도 큽니다.
따라서 더 효율적인 접근 방식은 페르마의 소정리(Fermat's Little Theorem)를 활용하는 것입니다.
페르마의 소정리는 다음과 같습니다.
a^(m-1) ≡ 1 (mod m), 단 m은 소수
이 정리를 이용하면 문제의 지수 B^C를 주어진 M에 대해 다음과 같은 형태로 변환할 수 있습니다.
x*(M-1) + y
페르마의 정리에 의해 A^(x*(M-1)) 항은 1이 됩니다. 따라서 전체 계산은 A^y의 값만 구하면 되는 문제로 단순화됩니다.
y의 값은 다음과 같이 구할 수 있습니다.
B^C = x*(M-1) + y
즉, y는 B^C를 (M-1)로 나누었을 때의 나머지입니다.
y = B^C % (M-1)
덕분에 결과는 다음 식만으로 손쉽게 구할 수 있게 됩니다.
(A ^ ((B^C) % (M-1))) % M
코드 구현 아이디어
여기에는 두 단계의 모듈러 거듭제곱이 필요합니다.
1단계: calcPowerMod(B, C, M-1)을 호출해 지수 부분인 B^C % (M-1)을 구합니다.
2단계: calcPowerMod(A, 위에서 구한 값, M)을 호출해 최종 결과를 얻습니다.
모듈러 거듭제곱 함수는 분할 정복(빠른 거듭제곱, Binary Exponentiation) 기법으로 O(log y) 시간 안에 계산됩니다. 지수를 절반씩 줄여가며, 지수가 홀수일 때는 결과에 밑수를 곱하고 짝수일 때는 밑수를 제곱하는 방식으로 진행합니다.
위 풀이의 동작을 보여주는 프로그램입니다.
예제 코드
#include<iostream>
using namespace std;
// x^y % p 를 빠른 거듭제곱으로 계산
int calcPowerMod(int x, int y, int p) {
int powMod = 1;
x = x % p;
while (y > 0) {
if (y & 1)
powMod = (powMod * x) % p;
y /= 2; // y = y/2
x = (x * x) % p;
}
return powMod;
}
// (A^(B^C)) % M 계산
int findPowerOfPowerMod(int A, int B, int C, int M) {
return calcPowerMod(A, calcPowerMod(B, C, M-1), M);
}
int main() {
int A = 3, B = 6, C = 2, M = 11;
cout << "소수 모듈로 거듭제곱의 거듭제곱 값: " << findPowerOfPowerMod(A, B, C, M);
return 0;
}실행 결과
소수 모듈로 거듭제곱의 거듭제곱 값: 3
정리
페르마의 소정리를 활용하면 지수를 (M-1) 법으로 축소할 수 있어, 매우 큰 지수를 가진 거듭제곱 연산도 오버플로우 없이 효율적으로 처리할 수 있습니다. 이 기법은 경쟁 프로그래밍과 암호학적 계산에서도 널리 사용되는 필수 개념이므로 꼭 익혀두시길 권장합니다.