곱셈 (백준 1629번 파이썬)

개인적으로 이해하는 데 너무 힘들었던 문제
프로그래밍에 수학이 정말 중요하다는 걸 다시 한 번 깨닫게 만들어준 문제
이해하는 데 도움준 재열띠 가영띠 감사링 호호

문제

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

입력

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

출력

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

예제 입력

10 11 12

예제 출력

4

풀이

이문제를 이해하려면 나머지 분배 법칙과 지수법칙을 먼저 알아야 한다.

지수 법칙
A^m+n = A^m x A^n

나머지 분배 법칙
(AxB)%C = (A%C) *(B%C) % C

이 문제의 예제에 적용을 해보면
a = 10 , b = 11 , c = 12
10^11 % 12
= ((10^5)%12 x (10^5)%12 x 10)% 12
= ((10^2)%12 x (10^2)%12 x 10) %12 x (10^2)%12 x (10^2)%12 x 10) %12 x 10) %12

이렇게 된다. ( 이게 이해가 안됐어 ㅠㅠ)

코드

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))

후기

이 문제가 이해가 되질 않아 다른 사람들의 코드를 봤는데도 이해가 되질 않아 정말 많은 시간을 쏟았다. 그래도 이해가 되질 않아 너무 속상했는데 친구들이 차근차근 설명해줘서 결국 이해돼 너무 행복쓰 ㅎㅎ