백준 / 곱셈 / 1629

Question

문제링크
Silver 1

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

Input

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

10 11 12

Output

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

4

Logic

기본 구조 : recursion

모듈로 곱셈 법칙과 지수법칙을 이용한다.

1. 모듈로 곱셈 : (A X B) mod C = ((A mod C) X (B mod C)) mod C
2. 지수 법칙 : A^(m+n) = A^m X B^n

1) (A^B)%C는 다음과 같이 변환할 수 있다.

• B가 홀수인 경우 : ((A^(B//2))%C X (A^(B//2))%C X A ) % C
• B가 짝수인 경우 : ((A^(B//2))%C X (A^(B//2))%C ) % C

이를 재귀를 이용하여 표현한다.

Code

from sys import stdin

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

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

print(func(a,b))