[Silver I] 곱셈 - 1629

문제 링크

성능 요약

메모리: 31120 KB, 시간: 40 ms

분류

분할 정복을 이용한 거듭제곱, 수학

제출 일자

2024년 2월 5일 18:52:25

문제 설명

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

입력

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

출력

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

풀이

a, b, c = map(int, input().split())

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

print(func(a, b))

처음에 그냥 무작정 a의 b거듭제곱에 c를 나눈 나머지를 반환하도록 작성했는데 시간초가가 나서 확인해보니 입력 데이터가 20억이었다.

시간복잡도를 줄이기 위해 재귀를 사용하였다.

a^20을 그냥 20번 곱하는 것 보다 `a^10 * a^10 = a^20` 으로 하면 총 곱하기 연산이 11번만 있으면 된다.

그래서 재귀를 통해 절반의 값을 곱하고, 만약 b가 홀수라면 a를 한번 곱해줘야 한다.