[BOJ / PYTHON] 1629. 곱셈

A, B, C = map(int, input().split())


def power(N, p):
    global C

    if p == 0:
        return 1

    half = power(N, p // 2)

    if p % 2 == 0:
        return ((half % C) ** 2) % C
    else:
        return (((half * N) % C) * (half % C)) % C


print(power(A, B))

풀이.

거듭제곱을 분할 정복을 통해서 해결하자.
수가 너무 커지는 것을 방지하기 위해서 제시된 조건인 C의 나머지 값을 분할 정복 계산식에 추가한다.