백준 1629 곱셈 - 파이썬

문제.

 

 

풀이.

분할정복 알고리즘을 이용하여 지수가 짝수 일때는 n^(지수/2) * n^(지수/2) 를 해주면 되고

지수가 홀 수 일때는 n^((지수-1)/2) * n^((지수-1)/2) * n 을 해주면 된다.

시간이 빡빡하기 때문에 함수 호출을 한번만 이용하여한다.

 

소스코드.

import sys

def div_con(num, index):
    if index == 1:
        return num % C
    power = div_con(num, index//2) # 미리 값 구하기
    if index%2 == 0:
        return power * power % C
    elif index%2 == 1:
        return power * power * num % C


A, B, C = map(int, sys.stdin.readline().split())

print(int(div_con(A, B)))