[백준][실버] 1629번 곱셈

📁문제 설명

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

---

📁입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

---

📁출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

---

📁입출력 예

입력

10 11 12

출력

4

---

📁풀이

import sys
a,b,c = map(int,sys.stdin.readline().split())

def multi (a,n):
  if n == 1:
      return a%c
  else:
      tmp = multi(a,n//2)
      if n %2 ==0:
          return (tmp * tmp) % c
      else:
          return (tmp  * tmp *a) %c
          
print(multi(a,b))

참고

a**b % c는 시간초과가 날 것이라 생각하고 있었다. 하지만 이 방법 말고는 생각이 나지 않아 구글에 찾아보니 분할 정복를 이용하여 푸는 문제였다. '분할 정복'...? 난 그딴거 몰라!! 나중에 한번 분할 정복에 대해 정리해보도록 하겠다.