[Baekjoon] # 1629: 곱셈

곱셈

문제

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

예제

• 입력

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

10 11 12

• 출력

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

4

---

Solution

def solution(x, y, n):
    if x == 1:
        return 1

    if y == 1:
        return x % n

    half = solution(x, y // 2, n)

    if y % 2 == 0:
        return (half * half) % n
    else:
        return (half * half * x) % n


def main():
    import sys

    input_line = sys.stdin.readline()

    x, y, n = map(int, input_line.split(" "))

    answer = solution(x, y, n)

    print(answer)


if __name__ == "__main__":
    main()

---

해결 방법

만약 우리가 A ^ B 를 직접 계산하려 하면 큰 수 연산이 발생해 연산 시간이 너무 길어진다.

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

우리는 거듭제곱의 성질을 이용해 시간 복잡도를 줄일 수 있다.

핵심 아이디어: 지수를 반으로 나누기

A ^ B (mod C) 를 구할 때, 거듭제곱의 성질을 활용하면 다음과 같이 나눌 수 있다.

1. B가 짝수일 경우

   A ^ B = A ^ (B / 2) * A ^ (B / 2) 이다.

   따라서 A ^ B (mod C) = A ^ (B / 2) * A ^ (B / 2) (mod C) 이다.

2. B가 홀수일 경우

   A ^ B = A ^ (B // 2) * A ^ (B // 2) * A 이다.

   따라서 A ^ B (mod C) = A ^ (B // 2) * A ^ (B // 2) * A (mod C) 이다.

이렇게 재귀적으로 B를 2로 나누다보면,

B / (2 ^ k) = 1이 되는 k의 값을 O(log B)의 시간 복잡도로 찾을 수 있다.

B가 10억이어도 2 ^ 30 ≈ 1000000000이므로 k = 30 정도로 계산의 수를 줄일 수 있다.

시간 복잡도 분석

이 알고리즘은 분할 정복 (Divide & Conquer) 방식으로 동작한다.

시간 복잡도는 O(log B) 이다.

---

의사 코드

Algorithm ModularExponentiation(x, y, n)
    // Base cases
    if y = 1 then
        return 1
    end if
    
    if y = 1 then
        return x mod n
    end if

    // Recursive case using divide and conquer
    // Calculate half of the exponentiation
    half = ModularExponentiation(x, y/2, n)
    
    // If exponent is even
    if y is even then
        return (half * half) mod n
    // If exponent is odd
    else
        return (half * half * x) mod n
    end if
End Algorithm

---

URL

• 곱셈