파이썬 백준 1629번: 곱셈

문제 

https://www.acmicpc.net/problem/1629

1629번: 곱셈

 

풀이

분할정복을 이용해서 풀었다.

B가 짝수일때 , A^B = A^(B/2) * A^(B/2) 이다.

B가 홀수일때, A^B=  A^(B/2) * A^(B/2) * A 이다.

import sys

def fast_power(base, exponent, modulus):
    result = 1
    base %= modulus
    while exponent > 0:
        # 지수가 홀수인 경우
        if exponent % 2 == 1:
            result = (result * base) % modulus
        exponent //= 2
        # base를 제곱
        base = (base * base) % modulus
    return result

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

기본적인 거듭제곱 알고리즘은 O(n)의 시간복잡도를 갖지만, 빠른 거듭제곱 알고리즘은 지수를 반으로 나누어 재귀적으로 계산함으로써O(logn)의 시간복잡도를 갖는다.