파이썬으로 2^(2^p) mod q 계산하기 — 효율적인 거듭제곱 나머지 구현

두 개의 정수 p와 q가 주어졌을 때, 2^(2^p) mod q의 값을 구하는 프로그램을 만들어 보겠습니다. 출력 결과는 반드시 정수여야 합니다.

예를 들어 p = 5, q = 6이 입력으로 주어진다면 출력은 4가 됩니다. 실제로 2^(2^5) = 2^32 = 4,294,967,296이고, 이 값을 6으로 나눈 나머지가 바로 4이기 때문입니다.

해결 접근 방법

• 결괏값 res를 다음과 같이 계산합니다: res = 2^(2^p) mod q
• 계산된 res를 반환합니다.

여기서 핵심은 파이썬의 내장 함수 pow()를 세 개의 인자와 함께 사용하는 것입니다. 일반적인 방법으로 2^(2^p)를 먼저 완전히 계산한 뒤 나머지를 구하면, 지수가 기하급수적으로 커져 매우 비효율적입니다. 반면 pow(밑, 지수, 모듈러) 형태로 호출하면 모듈러 거듭제곱(modular exponentiation) 알고리즘이 적용되어 중간값을 항상 작게 유지하면서도 빠르게 결과를 얻을 수 있습니다.

구현 예시

아래 코드를 통해 더 쉽게 이해할 수 있습니다.

def solve(p, q):
    res = pow(2, 2 ** p, q)
    return res

print(solve(5, 6))

입력

p = 5, q = 6

출력

4

이처럼 pow() 함수의 세 번째 인자만 활용하면 아주 큰 거듭제곱 값도 메모리 부담 없이 나머지 연산을 수행할 수 있으며, 시간 복잡도 또한 O(log 지수) 수준으로 효율적입니다.