[알고리즘 문제풀이] 곱셈

문제 제목 : 곱셈

문제 난이도 : 하

문제 유형 : 분할정복, 재귀

https://www.acmicpc.net/problem/1629
시간 제한 : 0.5초
메모리 제한 : 128MB

문제풀이 아이디어

< 소스코드 >

a, b, c = map(int, input().split(' '))

def multi(a, n):
    if n == 1:
        return a % c
    else:
        temp = multi(a, n//2)
        if n % 2 == 0: # 짝수일 경우
            return (temp * temp) % c
        else: # 홀수일 경우
            return (temp * temp * a) % c
        
print(multi(a, b))