곱셈 (분할정복)

문제

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

입력

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

출력

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

 

예제입력

10 11 12

 

예제출력

4

 

- 풀이 방법

읽기 싫게 되어 있는데 시간이 지나면서 좀 더 나아질 예정!

모듈러성질의 A를 C로 나눴을 때의 나머지를 구하는 식과 B를 C로 나눴을 때의 나머지를 구하는 식으로 증명을 한다.

그래서 (A X B) mod C = (A mod C) (B mod C) modC가 나오므로

입력 예제를 보면, 10^11 % 12를 구하는 과정인데

제곱수를 2개로 나눠 실제 식 연산을 2개씩 분할해 부담을 줄이는 방식으로 재귀를 풀 수 있다는 생각이 든다.

 

그러나 조건이 있는데

만약 제곱수가 홀수라면, 2로 나누면 정수가 아닌 소수가 나오므로

현재 10^11 % 12의 경우

return (10) x (10^5 % 12) x (10^5 % 12) ... ①

return (10) x ( (10 % 12) x (10^2 % 12) x (10^2 % 12) ) x ( (10 % 12) x (10^2 % 12) x (10^2 % 12) ) ... ②

.... 으로 위 방식으로 재귀식을 만들 수 있다.

 

그런데 여기서 또 중요한 개념이 한가지 더 있는데,

만약 

return할 때 재귀를 그대로 2개를 넣으면 재귀 과정을 2배로 더 하게 되는 부담이 생기므로

1번에서 10^5 % 12는 따로 변수로 값을 받아놓아 그 변수값을 곱하는 형태로 사용해야 부담이 덜하다. (같은 계산과정이 2배가 되는것을 방지하기 위함)

 

A, B, C = map(int, input().split())

# 10^11 => 10 x (10^5)^2
def multiple(A, B, C) :
  if B == 1 :
    return A % C
  # 짝수
  tmp = multiple(A,B//2,C) % C
  if B % 2 == 0 :
    return (tmp * tmp) % C
  # 홀수
  else :
    return (A * tmp * tmp) % C
  
print(multiple(A, B, C))