<백준> 1629번 파이썬 알고리즘 [분할정복]

import sys

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

def pow(a, b):
  if b == 1:
    return a % c
  
  tmp = pow(a, b // 2)
  
  if b % 2 == 0:
    return tmp * tmp  % c
  else:
    return tmp * tmp * a % c


print(pow(a, b))

 

문제를 통해 시간을 줄일 수 있는 부분은 b!!

a * a * a * a * a ..... 연속적이면 시간소모가 큼

따라서 나눠서 곱함(a, b = 5, 4 -> (5^2) * (5^2))

완전 이진트리 모양으로 생각하면 편함