백준 1009 - 분산처리 (Python3)

코드

# 테스트 횟수 
T = int(input())

# 테스트 반복
for _ in range(T):
    a, b = map(int, input().split())

    # a ** i
    i = 1
    
    # a ** i를 수행하여 나오는
    # 1의 자리 숫자들을 담을 리스트
    lst = []
    
    
    while True:
        # a ** i 수행 결과의 1의 자리 숫자를 담을 변수
        k = a**i % 10

        # 벌써 lst에 담겨있는 경우라면 break
        # 기존에 담겨있다는 것은 곧 앞으로 나오는 값들 또한
        # 이미 담겨있는 숫자라는 의미
        if k in lst:
            break

        # 위의 조건문으로 걸러지지 않는 경우에만 lst에 추가
        lst.append(k)
        
        # i를 1씩 증가
        i += 1
        
    # b를 전체 리스트 길이 - 1로 모듈러 연산을 수행하면
    # a**b의 1의 자리 숫자를 구할 수 있음
    if lst[b % len(lst) - 1] == 0:
        print(10)
    else:
        print(lst[b % len(lst) - 1])

문제 해설

n번 데이터는 [n의 첫째 자리수 번호의 컴퓨터]가 처리하므로 (0인 경우 10번 컴퓨터) a의 b승 번째 데이터는 a의 b승의 첫째 자리수 번호의 컴퓨터가 처리할 것이다. 이것을 매우 단순하게 a의 b승을 연산한 후 마지막 숫자를 구해서 결과를 출력하면 너무 당연하게 시간 초과가 발생한다.

시간 초과를 해결하기 위하여 아래와 같은 방법을 사용하였다.

---

a라는 숫자를 계속 해서 거듭제곱을 수행하다보면 반복적으로 1의 자리 숫자가 나오는 것을 알 수 있는데, 이 숫자들을 리스트에 담아주고 b 를 리스트 전체 길이로 모듈러 연산을 수행한 후 -1을 해주면 원하는 답이 나온다.

• 리스트의 길이 : 거듭 제곱을 하여 나오는 1의 자리 숫자의 반복 주기
• b % 리스트의 길이 - 1 : a를 b번 거듭제곱했을 때 나오는 1의 자리 수

---