[Python] 백준 #1629 - 곱셈

문제

---

https://www.acmicpc.net/problem/1629

1629번: 곱셈

 

 

 

풀이

---

def go(a,b):
    if b==1: return a 
    sol = go(a,b//2) # 재귀 (이때 b//2로 해준다.) 
    sol = (sol*sol)%c # 곱해준다.
    if b%2: sol = (sol*a)%c # b가 홀수이면 한번 더 곱해야한다
    return sol%c

a,b,c = map(int,input().split())
print(go(a,b)%c)

 

 

분할 정복문제로 메모이제이션을 사용하였다.

1 ) 2의 10승을 2의 5승 * 2의 5승으로 나눠준다.

2 ) 2의 5승을 2의 2승 * 2의 2승 * 2 로 나눠준다.

3 ) 2의 2승을 2의 1승 * 2의 1승 으로 나눠준다.