[백준, python] 1629번 - 곱셈

백준 문제풀이 시작

---

문제

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

입력

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

출력

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

---

풀이

풀이 확인하기

문제를 얼핏 보면 매우 쉬운 문제같지만 시간 제한에 주목하면 평범한 방식으로는 절대 통과하지 못함을 알 수 있다. 그래서 우리는 중고등학교에서 배웠던 지수법칙을 응용할 것이다.

이때 지수법칙이란
\({x^n}\times{x^m} = {x^{n+m}}\) 인데 이를 제곱 식에 맞게 잘 응용하면

\[{x^n}= \begin{cases} x^{\frac{x}{2}}\times x^{\frac{x}{2}} & \text{if } \,\, n \% 2 = 0, \\ x^{\frac{x}{2}}\times x^{\frac{x}{2}}\times {x^1} & \text{if } \,\, n \% 2 = 1 . \end{cases}\]

의 형태로 바꿀 수 있다. 이렇게 계산을 할 경우 기존 거듭제곱보다 훨씬 적은 양의 계산만 가지고도 거듭제곱을 풀 수 있다.

이를 프로그램에 옮겨 문제가 원하는 요구사항대로 출력하면 풀 수 있다.

import sys
input = sys.stdin.readline

def mul(a, b, c):
    if (b == 1):
        return a % c
    else:
        s = mul(a, b//2, c)
        x = s*s
        if(b % 2 == 0):
            return x % c
        else:
            return (x * mul(a, 1, c)) % c
    
a, b, c = map(int, input().split(" "))
print(mul(a, b, c))

P.S. 원래는 문제를 풀 때 mul 함수에선 거듭제곱만 구하고 이후 마지막 수로 나눈 나머지를 구했는데, 이렇게 할 경우 시간 초과가 발생한다. 그래서 함수 내에 옮기니까 시간 제한이 걸리지 않고 통과함을 알 수 있었다. 왜 그런지는 찾아보아야 할 듯 하다.

• baekjoon
• python