백준 | 곱셈

백준 곱셈

파이썬에서 A ** B 연산은 O(log B)의 시간 복잡도를 갖는다.

그런데 A, B, C 모두 2,147,483,647 이하의 자연수이므로, (A ** B) % C를 직접 계산하면, 큰 수 연산으로 메모리 초과가 발생할 수 있다.

# 오답(시간 초과 및 메모리 초과 발생 가능)


import sys

a, b, c = map(int, sys.stdin.readline().split())

print((a ** b) % c)

따라서 연산 횟수를 줄여야 하는데, 이는 거듭제곱의 성질을 이용한 분할 정복(Exponentiation by Squaring)을 통해 해결할 수 있다.

예를 들어, 2 ** 32을 구하는 과정을 보자.

일반적으로는 2를 32번 곱하는 것이므로, 총 32번의 연산이 필요하다.

그런데 2 ** 32를 (2 ** 16) ** 2로 보면.. 2 ** 16을 먼저 구한 뒤, 제곱하는 것이므로, 연산 횟수가 17번으로 줄어든다.

이를 반복하면 O(B)만큼의 연산을 O(log B)로 최적화할 수 있다!

# 정답


import sys

def power(a, b, c):
    if b == 0:
        return 1
    
    half = power(a, b // 2, c)
    half = (half * half) % c

    if b % 2 == 0:
        return half
    else:
        return (half * a) % c

a, b, c = map(int, sys.stdin.readline().split())

print(power(a, b, c))

또한, 파이썬의 pow(A, B, C)는 모듈러 연산이 최적화된 거듭제곱 함수로, 내부적으로 분할 정복을 사용하기 때문에, 시간 초과가 발생하지 않는다!

# 정답


import sys

a, b, c = map(int, sys.stdin.readline().split())

# pow(base: int, exp: int, mod: int) -> int
print(pow(a, b, c))