[파이썬] 백준 1629 곱셈

< 해결 방법 >

 

시간 초과가 계속 나서 구글링 했다. 분할을 한 후 푸는 과정인데 내용은 어렵지 않았지만 낯선 풀이었다.

 

import sys
 
def dac(a,b,c):
    if b==1:
        return a%c
    elif b%2==0:
        return (dac(a,b//2,c)**2)%c
    else:
        return ((dac(a,b//2,c)**2)*a)%c
 
 
 
a,b,c = map(int,sys.stdin.readline().rstrip().split(" "))
 
print(dac(a,b,c))