C++에서 재귀 함수로 2^(2^A) % B 값 구하기

이 튜토리얼에서는 수식 2^(2^A) % B의 값을 계산하는 프로그램을 작성해 보겠습니다.

2^(2^A)처럼 지수가 기하급수적으로 커지는 경우, 실제 거듭제곱 값을 직접 계산하는 것은 불가능합니다. 하지만 다음과 같은 수학적 관계를 활용하면 재귀 함수를 통해 효율적으로 나머지 값을 구할 수 있습니다.

2^(2^A) = (2^(2^(A-1)))^2

즉, 한 단계 아래의 결과를 제곱하고 B로 나눈 나머지를 취하면 되므로, 모듈러 연산의 성질 덕분에 오버플로우 없이 계산할 수 있습니다.

문제 해결 절차

A와 B 두 개의 인자를 받는 재귀 함수를 작성합니다.
- A가 1이면 4 % B를 반환합니다. (2^(2^1) = 4이므로)
- 그렇지 않으면 A-1과 B를 인자로 전달하여 함수를 재귀 호출합니다.
- 반환된 결과에 대해 result² % B를 계산하여 반환합니다.
최종 결과를 출력합니다.

예제 코드

위 로직을 C++ 코드로 구현하면 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;

long long solveTheEquation(long long A, long long B) {
    // 2^(2^1) % B = 4 % B
    if (A == 1) {
        return (4 % B);
    }
    else {
        long long result = solveTheEquation(A - 1, B);
        return result * result % B;
    }
}

int main() {
    long long A = 37, B = 467;
    cout << solveTheEquation(A, B) << endl;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

동작 원리 정리

이 알고리즘은 A번의 재귀 호출만으로 답을 구하며, 각 단계에서 값이 항상 B 미만으로 유지되기 때문에 long long 범위 내에서 안전하게 연산됩니다. 시간 복잡도는 O(A), 공간 복잡도 역시 재귀 호출 스택으로 인해 O(A)입니다.

마무리

이 튜토리얼에 대해 궁금한 점이 있다면 댓글 섹션에 남겨 주세요.