백준 1629번 문제 풀이(python)

접근

A, B, C 모두 32비트 int 범위(약 21억)까지 표현할 수 있다.

 

문제를 그대로 접근해 보면,

X = (A ** B) % C

1. A를 21억 번 곱해야 하므로 시간복잡도가 안된다.

2. 21억의 거듭제곱 과정에 오버플로우가 고려된다.

 

풀이

해결해 보자.

1. (지수 법칙 활용) 지수를 쪼개 시행 횟수를 줄인다.

A**30 = (A**15)**2

A**15 = (A**7)**2 * A

A**7 = (A**3)**2 * A

A**3 = (A**1)**2 * A

A**1 = A

 

보통 매 단계마다 값이 절반으로 줄어들 때,

마지막까지 도달하는 데 필요한 시행 횟수는 로그 시간 복잡도 O(log N)로 표현한다.

100 → 50 → 25 → 12 → 6 → 3 → 1

log₂100 ≈ 6.64

 

1까지 내려가는 각 단계마다 제곱 연산이 있으므로 전체 연산 횟수는 2 log N 정도가 되고, 홀수 일 때 추가곱셈은 + C

따라서 총 연산 횟수는 O(2 log N + C) ≈ O(log N)로 근사할 수 있다.

 

2. (모듈러 연산 법칙 활용) 계산 과정의 최대값을 C**2 수준으로 유지한다.

Long 자료형(64비트)을 사용할 경우, 32비트 최댓값인 약 21억의 제곱까지는 표현할 수 있으므로, 계산 과정의 상한을 C**2 수준으로 고려한다.

(A⋅B) mod M=((A mod M)⋅(B mod M)) mod M (곱셈 성질)

A**K mod M = ((A mod M)**K) mod M (거듭제곱 성질)

 

A**30 mod M = (A**15)**2 mod M

A**15 mod M = ((A**7)**2 * A) mod M = (((A**7)**2)) * (A mod M)) mod M

A**7 mod M = ((A**3)**2 * A) mod M = ...

A**3 mod M = ((A**1)**2 * A) mod M = ...

A**1 mod M = A mod M

 

A**k mod M의 최댓값은 M-1이다. (예: M=21억, A=21억-1)
그래서 과정에 거듭제곱까지는 문제 되지 않는다. 다만 k가 홀수일 경우 A를 한 번 더 곱해야 하므로, 최대 M**3 수준까지 커질 수 있다.
여기서 곱셈의 성질을 활용해 (M-1)**2 mod M 를 먼저 계산하면, 이후 연산은 (M-1) * A ≈ M**2 범위 안에서 수행할 수 있다.

 

코드

import sys

# a = 밑, b = 지수
def recur(a, b, c):
    if (b <= 2):
        return (a**b) % c

    # 짝
    if (b%2 == 0):
        return (recur(a, b//2, c)**2) % c
    # 홀
    else:
        t = (recur(a, b//2, c)**2)
        return ((t%c) * (a%c)) % c


A, B, C = map(int, sys.stdin.readline().split())
print(recur(A, B, C))