[백준, BOJ] 1009 - 분산처리

1. Question

재용이는 최신 컴퓨터 10대를 가지고 있다. 어느 날 재용이는 많은 데이터를 처리해야 될 일이 생겨서 각 컴퓨터에 1번부터 10번까지의 번호를 부여하고, 10대의 컴퓨터가 다음과 같은 방법으로 데이터들을 처리하기로 하였다.

1번 데이터는 1번 컴퓨터, 2번 데이터는 2번 컴퓨터, 3번 데이터는 3번 컴퓨터, ... ,

10번 데이터는 10번 컴퓨터, 11번 데이터는 1번 컴퓨터, 12번 데이터는 2번 컴퓨터, ...

총 데이터의 개수는 항상 ab개의 형태로 주어진다. 재용이는 문득 마지막 데이터가 처리될 컴퓨터의 번호가 궁금해졌다. 이를 수행해주는 프로그램을 작성하라.

1.1 Input

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a < 100, 1 ≤ b < 1,000,000)

1.2 Output

각 테스트 케이스에 대해 마지막 데이터가 처리되는 컴퓨터의 번호를 출력한다.

1.3 Example

입력

5
1 6
3 7
6 2
7 100
9 635

출력

1
7
6
1
9

2. Approach

이전 포스팅에서 소개한 거듭제곱 형태의 자연수의 나머지를 요구하는 문제이다.

처음에는 완전 생코드를 따로 짜다가 안돼서 두번째에 그냥 $O(n)$짜리를 박아넣었다. 그래도 안돼서 이전 포스팅 코드랑 비교하다가... 나머지가 0으로 끝나면 10으로 출력을 해야한다는 것을 알았다.... 뻐킹

3. Submission

4. Code

def powMod(base, index):
    r = 1
    while index:
        if index & 1:
            r = (r * base) % 10
        base = base ** 2 % 10
        index >>= 1
    return r

T = int(input())

for _ in range(T):
    a, b = map(int, input().split())
    ans = powMod(a, b)
    if not ans:
        ans = 10
    print(ans)