곱셈

문제

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

입력

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

출력

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

예제 입력 1

10 11 12

예제 출력 1

4

문제 접근 과정

이 문제는 학창시절에 수학 공부를 좀 했다면 풀수도 있었을것같다.

나머지 분배 법칙과 지수 법칙을 알아야 한다.

곱셈 (백준 1629번 파이썬)

여기서 간단히 지수법칙과 나머지 분배법칙에 대한 공식이 나오는데 간단히 서술해보자면 아래와 같다.

지수 법칙

A^m+n = A^m x A^n

나머지 분배 법칙

(AxB)%C = (A%C) *(B%C) % C

여기서 주의할 점은 이 문제에서의 b 즉, 어떤수의 지수가 홀수일때와 짝수일때를 구분해주어야 한다는 점이다.

홀수라면 둘로 나눈 후에 하나를 다시 곱해주어야한다.(a^11 = a^5 a^5 a)

최종 코드

from sys import stdin

a,b,c = map(int, 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))

이 문제를 풀면서 공부한 내용

• 지수 법칙
• 나머지 분배 법칙

여담

곱셈 (백준 1629번 파이썬)

이 문제를 설명해준 블로그를 들어갔는데 우연히 정글 선배님의 블로그였다.

덕분에 완전 이해되었다.

선배님 감사합니다! ㅎㅎ🙇🏻