백준 문제 풀이 - 분산처리 1009번

📜 문제 이해하기

재용이는 최신 컴퓨터 10대를 가지고 있다. 어느 날 재용이는 많은 데이터를 처리해야 될 일이 생겨서 각 컴퓨터에 1번부터 10번까지의 번호를 부여하고, 10대의 컴퓨터가 다음과 같은 방법으로 데이터들을 처리하기로 하였다.
1번 데이터는 1번 컴퓨터, 2번 데이터는 2번 컴퓨터, 3번 데이터는 3번 컴퓨터, ... ,
10번 데이터는 10번 컴퓨터, 11번 데이터는 1번 컴퓨터, 12번 데이터는 2번 컴퓨터, ...
총 데이터의 개수는 항상 ab개의 형태로 주어진다. 재용이는 문득 마지막 데이터가 처리될 컴퓨터의 번호가 궁금해졌다. 이를 수행해주는 프로그램을 작성하라.

💡 문제 재정의

데이터의 수가 주어졌을 때 마지막으로 처리하는 컴퓨터가 어떤 컴퓨터인지 출력하라

✏️ 계획 수립

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

💻 계획 수행

import sys

if __name__ == '__main__':
    T = int(sys.stdin.readline().rstrip())

    for _ in range(T):
        a, b = map(int, sys.stdin.readline().split())
        if a % 10 == 0:
            print(10)
        else:
            bin_b = int(format(b, 'b'))
            index = 0
            mod = 10

            # 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)

🤔 회고

다루는 수의 지수가 매우 크고 mod 연산을 할때는 연속제곱법을 사용할 수 있음을 기억하자.