[BOJ] 1009번: 분산처리

 

문제에서 주어진 상황을 분석하면 10 단위로 컴퓨터 번호가 반복되는 것을 볼 수 있다.

입력으로 받은 수에서 일의 자리 수를 알아내는 것이 관건이다.

항상 데이터의 개수가 a^b 형태로 주어지는데, 문제가 있다.

문제 조건에서 b를 보면 1,000,000까지 입력이 들어올 수 있으므로 일일이 계산하기는 불가능하다.

따라서 a와 b 만으로 필요한 정보를 얻어야한다.

먼저 a의 경우를 보자.

a값에 따라 일의 자리 수에서 나타나는 규칙(수열)이 다름을 알 수 있다.

예를 들면,

1의 경우는 거듭제곱을 계속 시도해도 계속 일의 자리의 수가 1이다.

2의 경우는 2, 4, 8, 6이 반복되는 구조다.

이런 식으로 1부터 9까지의 거듭제곱을 시도할 때 반복되는 수열을 2차원 배열로 저장한다.

다만 a 역시 100까지 입력이 들어올 수 있으므로 이 부분도 생각이 필요하다.

a를 10으로 나눠보자.

a를 10으로 나눈 나머지는 a의 일의 자리 수를 의미한다.

그리고 a의 일의 자리 수에 따라 a^b의 일의 자리 수에서 나타나는 규칙을 알 수 있다.

왜냐하면 일의 자리 수는 일의 자리 수끼리 곱해서 결과가 나오기 때문이다.

간단하게 53*53을 생각해보면 계산 결과는 모를지라도 일의 자리 수는 3*3=9임을 알 수 있다.

a의 일의 자리 수	a^b의 일의 자리 수에서 나타나는 규칙
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
0	0 (=10번째 컴퓨터)

이제 이 수열이 몇 번 반복되는지를 세면 된다.

총 거듭제곱하게 되는 횟수는 b이므로

내가 찾고 있는 수는 수열의 (b % 수열의 길이) 번째 수다.

말이 좀 헷갈릴 수 있다. 예를 들어 설명해보겠다.

---

<예시>

a=52, b=7라고 하자.

a가 52이고 52 % 10 = 2이므로 일의 자리 수에서 나타날 수 있는 수들은 [2, 4, 8, 6]이다.

b가 7이므로 총 7번의 거듭제곱을 하게 된다.

따라서 내가 찾는 수는 수열 중에서 7번째로 오는 수일 것이다.

2, 4, 8, 6, 2, 4, 8, 6, ...

따라서 답은 8번째 컴퓨터라고 쓸 수 있다.

하지만 b는 이보다 훨씬 클 수 있다.

따라서 매번 이렇게 늘어놓고 세어볼 수는 없다.

수열을 자세히 들여다 보면 4번씩 반복되는 것을 알 수 있다.

따라서 4번씩 반복할 수 있는 만큼 최대한 반복하고 남은 나머지가 내가 찾는 수의 위치다.

7을 수열의 반복되는 길이인 4로 나눠 보자.

그럼 나머지는 3이 된다.

[2, 4, 8, 6] 에서 바로 3번째가 내가 찾는 수이다.

 

---

이를 코드로 옮기면 다음과 같다.

#1009.py
T = int(input())

for _ in range(T):
    a, b = map(int, input().split())
    table = [
        [1],
        [2, 4, 8, 6],
        [3, 9, 7, 1],
        [4, 6],
        [5],
        [6],
        [7, 9, 3, 1],
        [8, 4, 2, 6],
        [9, 1]
    ]
    if (a % 10 == 0):
        print(10)
        continue
    i = a % 10 - 1
    length = len(table[i])
    ans = table[i][b % length - 1]
    print(ans)