[백준][Python] 1629 곱셈

분할정복 대표적인 문제이다.

연산 갯수를 줄이기 위해 반으로 쪼개고 쪼개 A*1로 쪼갠다음 그 결과값을 양쪽에서 곱해주면서 조합해준다.

분할 : 곱해야 하는 갯수 B를 2로 나누어 주며 분할한다.

정복 : A*1의 정복을 통해 계산한다.

조합 : A*A / (A*A) * (A*A) / 이런식으로 결과값을 제곱하면서 올라와 모든 재귀가 끝나면 연산이 끝난다.

import sys
input = sys.stdin.readline

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

# 정복
def conq(length):
    # 정복 : length가 1이 되면 A를 반환하겠다.(최소단위 연산의 정복)
    if length == 1:
        return A %C
        # 짝수면 좌우로 찢고
    if length % 2 == 0:
        # 분할 (곱해야하는 length를 반으로 나눠가며 계산하겠다.)
        left = conq(length // 2)
        # 조합(함수 반환시마다 양쪽을 곱해서 올라가겠다.)
        return left * left %C
        # 홀수면 좌우로 찢고 남은A하나 곱해준다.
    else:
        left = conq(length // 2)
        return left * left * A %C


print(conq(B))