백준 문제 풀이 - 곱셈 1629번

📜 문제 이해하기

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

💡 문제 재정의

A^B(mod c)를 구하자.

✏️ 계획 수립

이 문제는 mod 10 연산을 하면 쉽게 구할수 있지만 이 문제의 핵심은 최대 2147483647^2147483647 비교할 수 있다는 것이다. 즉, 값이 커지면 오버플로우가 일어나거나 시간이 오래걸린다는 것이다. 따라서 연속제곱법을 사용해서 수를 잘게 쪼개고 연산하면 된다.

💻 계획 수행

import sys

if __name__ == '__main__':
    a, b, mod = map(int, sys.stdin.readline().split())
    bin_b = int(format(b, 'b'))
    index = 0

    # base case
    mod_b = [a % mod]
    temp_b = bin_b // 10

    # common case
    while temp_b > 0:
        mod_b.append((mod_b[index] ** 2) % mod)
        temp_b = temp_b // 10
        index += 1

    index = 0
    result = 1
    while bin_b > 0:
        val = bin_b % 10
        bin_b = bin_b // 10

        if val:
            result *= mod_b[index]
        index += 1

    print(result % mod)

🤔 회고

바로 전 문제를 풀면서 적용할 수 있는 문제를 풀어보았다. 똑같이 연속제곱법을 사용하면 문제를 풀 수 있다.