[백준-1629] 곱셈 / Python

1629번: 곱셈

import sys

input = sys.stdin.readline

a, b, c = map(int, input().split())


def func(length):
    if length == 1:
        return a % c
    if length % 2 == 0:
        temp = func(length // 2)
        return temp * temp % c
    else:
        temp = func(length // 2)
        return temp * temp * a % c


print(func(b))

 

해설

기본 연산이나 반복문으로 풀면 시간 초과가 걸린다.

분할정복을 이용하여 해결했다.