[Baekjoon] 1629번 : 곱셈

1. 문제

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

• 분할 정복 문제

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

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

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

// 예제 입력 1 
10 11 12

// 예제 출력 1 
4

2. 핵심 아이디어

• 시간초과 문제를 해결하기 위해 분할 정복 사용

3. Python 문제풀이

import sys
input = sys.stdin.readline

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

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

print(solution(a, b))

4. Java 문제풀이