[Baekjoon/Python] 1629번: 곱셈 - 효과는 굉장했다!

1629번: 곱셈

 

알고리즘 분류

• 수학
• 분할 정복을 이용한 거듭제곱

 

 

SOLUTION

pow() 함수를 이용한 간단한 코드

print(pow(*map(int,input().split())))

 

 

분할 정복 이용한 코드

import sys

def divide_and_conquer(num, n):
    if n == 1:
        return num % C
    
    if n % 2 == 0:
        y = divide_and_conquer(num, n//2)
        return y * y % C
    
    else:
        y = divide_and_conquer(num, (n-1)//2)
        return y * y * num % C


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