백준 - 1629번(분할정복, 분할곱)

import sys
a,b,c = sys.stdin.readline().split()

a = int(a)
b = int(b)
c = int(c)

def dac(a,b):
    if b ==1:
        return a % c
    temp = dac(a,b//2)

    if b%2 == 0:
        return temp*temp %c

    else:
        return temp*temp * a %c

print(dac(a,b))

temp를 통해서 절반씩 반복해서 계산하게 재귀를 호출한다.

곱해지는 횟수가 홀수번이라면 한 번이 남기에 a를 곱해준다.