거듭제곱 분할정복

# 11^12를 구해야하면 
# exp(11,12)를 하면 됨
# 실제 사용시 recursion함수이기에 recursion error와 
# 나머지를 return 하라는 문제조건 등에 유의하기
# ps: 나머지를 return 해야할시 return이 붙은 모든곳에서 나누어주어야함!!
def exp(base: int, expo: int) -> int:
    if expo == 0:
        return 1
    if expo == 1:
        return base
    a = exp(base, expo//2)
    b = expo%2
    # print(f'a,b = {a,b}')
    return a*a*(base**b)

print(exp(2,0))​