Baekjoon Online Judge 1629번 파이썬. 분할 정복.

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

1629번: 곱셈

A^(m+n) = A^m * A^n
(A*B)%C = (A%C)*(B%C)%C
위의 지수법칙. 분배 법칙을 알아두어야 한다.

정답 코드

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

def solution(a,b,c):
  if b == 1: #a의 1제곱이면.
    return a%c
  N = solution(a,b//2,c) # a^(b//2) 구하기
  if b % 2 == 0: #b가 짝수
    return N*N%c #지수 법칙 사용
  else: #b가 홀수
    return N*N*a%c #지수 법칙 사용
    
print(solution(A,B,C))