백준 1629 곱셈, 파이썬

문제

문제를 처음 읽고는 혹시나 하는 마음에 이렇게 코드를 제출해봤지만 역시나 시간 초과였다.

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

print(A ** B % C)

이 문제를 해결하기 위해서는 분할정복을 활용해야 한다.

1. 지수가 짝수일 때
2. 지수가 홀수일 때

코드

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

def find(a, b):
    # b가 1이라면, a 나누기 C 리턴
    if b == 1:
        return a % C
    else:
        tmp = find(a, b // 2)
        if b % 2 == 0:
            return (tmp * tmp) % C
        else:
            return (tmp * tmp * a) % C

print(find(A, B))