[백준] #1009 분산처리(Python)

 

주어진 a를 b만큼 거듭제곱했을 때의 일의 자리에 있는 수를 구하는 문제이다. 

직접 거듭제곱을 해서 일의 자리를 구하는 방법이 당연하게도(?) 먼저 떠올랐지만 정답비율을 보고 바로 생각을 접었다.

 

0~9까지의 각 숫자를 거듭 제곱하다 보면 일의 자리 숫자가 규칙성을 갖고 변하는 것을 볼 수 있다.

0 : 0

1: 1

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

3: 3, 9, 7, 1, 3, 9, 7, 1 .. 

4: 4, 6, 4, 6, ...

...

이런식으로 일의 자리 숫자가 규칙적으로 나타난다.

이러한 규칙을 갖는 숫자들을 nums라는 리스트에 담아서 저장했다. 

nums는 [[0],[1],[2,4,8,6],[3,9,7,1],[4,6], ... , [8,4,2,6], [9,1]] 와 같은 형태를 갖게 된다. 

a의 일의 자리(a_)를 nums의 인덱스로 사용(nums[a_]) 하고,

거듭제곱해야 할 수(b)를 그 리스트의 길이만큼 나누고 난 뒤의 나머지(rem)를 그 리스트의 인덱스로 사용하면 답이 나온다.

 

이때 주의해야 할 것은 0번 컴퓨터는 없고, 10번 데이터는 '10번 컴퓨터'에서 처리된다. 

즉 1의 자리가 0일 때 따로 처리를 해야 한다.

처음에 이것 때문에 한번 틀렸다 ㅎㅎ... 문제를 잘 읽자

nums[0][0] 값을 10으로 바꾸거나, 1의 자리가 0이면 10을 출력하는 방법으로 해결할 수 있다.

T = int(input())

nums = [[i] for i in range(10)]  # 0부터 9까지 하나씩 들어있는 리스트 만들기

'''
거듭제곱의 1의 자리 수는 반복된다는 특징이 있다.
직접 거듭제곱을 해서 찾으면 메모리가 터질 수 있으므로
반복되는 1의 자리 숫자들만 찾아서 리스트에 순서대로 넣었다.
'''
for i in range(10):
    x = 2
    while True:
        if int(str(i**x)[-1]) in nums[i]: 
            break
        last_num = str(i**x)[-1]
        nums[i].append(int(last_num))
        x += 1

for i in range(T):
    a, b = map(int, input().split())
    a_ = int(str(a)[-1])        # 1의 자리만 쓸 것이다.
    # 거듭제곱 해야할 값(b)을 리스트 안에 있는 개수만큼 나눠줬을 때의
    # 나머지를 찾으면 된다.
    if a_ == 0:                 # 끝자리 0일 경우 10 출력
        print(10)
    else:    
        div_num = len(nums[a_])     # 1의 자리 숫자에 따라 나눠야할 리스트 길이가 다르다.
        rem = b % div_num    
        print(nums[a_][rem-1])

 

문제 링크

https://www.acmicpc.net/problem/1009