백준 1629 파이썬(Python) 문제풀이 곱셈

문제링크:https://www.acmicpc.net/problem/1629

1629번: 곱셈

다루는 주제: 분할 정복

import sys

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

# A * A * A * A ... * A % C로 문제를 풀고자 했으면 시간 초과
# A**B%C를 (A**B//2) * (A**B//2) * C 이런식으로 곱셈 계산을 최소화
def calc(a, b):
    if b == 1:
        return a % C
    else:
        temp = calc(a, b // 2)  # ex) 10^10 == 10^5*10^5
        if b % 2 == 0:  # b가 짝수일때 계산식
            return temp * temp % C
        else:  # b가 홀수일떄 계산식
            return temp * temp * a % C


print(calc(A, B))