[BOJ] 분산 처리 - 1009 (B2)
| 시간 제한 | 메모리 제한 |
|---|---|
| 1 초 | 128 MB |
문제
재용이는 최신 컴퓨터 10대를 가지고 있다. 어느 날 재용이는 많은 데이터를 처리해야 될 일이 생겨서 각 컴퓨터에 1번부터 10번까지의 번호를 부여하고, 10대의 컴퓨터가 다음과 같은 방법으로 데이터들을 처리하기로 하였다.
1번 데이터는 1번 컴퓨터, 2번 데이터는 2번 컴퓨터, 3번 데이터는 3번 컴퓨터, … ,
10번 데이터는 10번 컴퓨터, 11번 데이터는 1번 컴퓨터, 12번 데이터는 2번 컴퓨터, …
총 데이터의 개수는 항상 $a^b$개의 형태로 주어진다. 재용이는 문득 마지막 데이터가 처리될 컴퓨터의 번호가 궁금해졌다. 이를 수행해주는 프로그램을 작성하라.
입력
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a < 100, 1 ≤ b < 1,000,000)
출력
각 테스트 케이스에 대해 마지막 데이터가 처리되는 컴퓨터의 번호를 출력한다.
풀이
주어진 숫자는 제곱의 형태로 주어지며 최대 $1000000^{100}$이 될 수 있기 때문에 컴퓨터로 처리하는 것을 모두 시뮬레이션하는 것으로는 시간 제한을 맞출 수 없다. 모두 확인하지 않고 어떤 컴퓨터가 처리했는지 알 수 있는 방법은 주어진 숫자의 1의 자리를 활용하는 것이다. 어떤 1의 자리의 수를 n번 곱하면 계산된 수의 1의 자리가 주기적으로 반복되는 것을 알 수 있고 그 수는 아래와 같이 나타낼 수 있다.
1
2
3
4
5
6
7
8
9
nums = {1 : [1],
2 : [2, 4, 8, 6],
3 : [3, 9, 7, 1],
4 : [4, 6],
5 : [5],
6 : [6],
7 : [7, 9, 3, 1],
8 : [8, 4, 2, 6],
9 : [9, 1]}
하지만 무턱대고 $a^b$를 계산해서 1의 자리를 구한다고 해도 중복되는 값들이 있기 때문에 정확히 어떤 수의 제곱인지 알 수 없다. 그래서 먼저 a를 nums의 키로 넣어 제곱 했을 때 1의 자리에 나올 값들을 추려내고 그 중 b번째 값을 답으로 출력한다. b번째 값이 답이 될 수 있는 이유는 a를 b번 곱하는 동안에 1의 자리의 값도 b번 바뀔 것이기 때문이다.
예를 들어 a가 124, b가 16이라고 하면 다음과 같은 과정을 거치게 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
n = int(input())
nums = {1 : [1],
2 : [2, 4, 8, 6],
3 : [3, 9, 7, 1],
4 : [4, 6],
5 : [5],
6 : [6],
7 : [7, 9, 3, 1],
8 : [8, 4, 2, 6],
9 : [9, 1]}
for _ in range(n):
a, b = map(int, input().split())
# a의 1의 자리수를 구한다 -> 4
one = a % 10
# 1의 자리에 나올 수 있는 값들을 가져온다 -> nums[4] -> [4, 6]
# 이 중에서 b번째 값을 취한다. 4, 6, 4, 6, 4, 6 -> 6
print(nums[one][(b - 1) % len(nums[one])])
단 a의 1의 자리가 0일 경우 무조건 제곱한 수의 1의 자리도 0이므로 10번 컴퓨터가 처리하게 된다.
1
2
3
4
a, b = map(int, input().split())
one = a % 10
if not one:
print(10)
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
n = int(input())
nums = {1 : [1],
2 : [2, 4, 8, 6],
3 : [3, 9, 7, 1],
4 : [4, 6],
5 : [5],
6 : [6],
7 : [7, 9, 3, 1],
8 : [8, 4, 2, 6],
9 : [9, 1]}
for _ in range(n):
a, b = map(int, input().split())
one = a % 10
if not one:
print(10)
else:
print(nums[one][(b - 1) % len(nums[one])])