[백준] 1629번: 곱셈 - [Python/파이썬]

문제

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

1629번: 곱셈

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

입력

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

출력

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

코드

import sys
a, b, c= map(int, sys.stdin.readline().split())
#분할정복의 아이디어 
def DaC(a, b):
    if b==1:
        return a%c

    tmp=DaC(a, b//2)

    if b%2==0:
        return tmp*tmp%c
    else:
        return tmp*tmp*a%c

print(DaC(a,b))

문제해결

아무 생각 없이 주어진 조건 그대로 풀면 쉽게 풀릴 수 있을 것 같지만 구하려는 수가 굉장히 커지기 때문에
분할정복의 아이디어를 쓰면 쉽게 풀린다,

이 문제를 풀기 위해 지수 법칙과 모듈러 성질을 알고있어야 풀 수 있다.

 

지수법칙 : a^(n+m) = a^n * a^m

모듈러 성질 : (a*b)%c = (a%c * b%c)%c

 

재귀 함수로 지수 B를 절반으로 계속 나눠서

짝수일 때 : tmp*tmp

홀수일 때 : tmp*tmp*a 로 지수법칙을 사용하여 시간복잡도를 O(log n)수준으로 낮춰주었다.

 

이런 법칙을 적용할 수 있는 구현력을 갖추면 풀수 있다,