[백준 BOJ_1629] 곱셈 Python 풀이

출처: 백준 온라인 저지

문제

풀이

분할정복을 이용해 거듭제곱을 더 빨리 계산할 수 있습니다.

주어진 지수를 반으로 나눈 지수만큼의 거듭제곱을 한 값을 두번 곱해주는 방식입니다. 지수가 홀수 일 경우에는 반으로 나눈 값을 두번 곱해준 뒤 n을 한번 더 곱해줍니다.

각 곱한 값을 C로 나눈 나머지로 반환해줍니다.

지수가 0(기저사례)일때는 모든 수의 0제곱의 값 1을 반환해줍니다.

코드

def power(n, exp):
    if exp == 0:
        return 1
    half = power(n, exp // 2)
    if exp % 2:
        return (half*half*n)%C
    return (half*half)%C
A, B, C = map(int, input().split())
print(power(A, B))