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

문제

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

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

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

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

입력

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

출력

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

예제 입력 1

5
1 6
3 7
6 2
7 100 
9 635

예제 출력 1

1
7 
6 
1
9

---

문제풀이

• 문제 자체는 간단하다.
  • a에b만큼 제곱한 수에서 10을나눈 나머지와 나머지가 0일때 10번컴퓨터라는 조건만 선언해주면 된다.
• 그런데? 입력조건을 보자 (1 ≤ a < 100, 1 ≤ b < 1,000,000) 으로 b의 값이 매우 크다. 시간제한이 1초인 문제인데 당연히 시간초과가 걸리는 문제.
• 1~9까지 끝자리?

  • 1	1,1,1,1....
    2	2,4,8,6,...
    3	3,9,7,1,..
    4	4,6,4,6,...
    5	5,5,5,5,...
    6	6,6,6,6,...
    7	7,9,3,1,....
    8	8,4,2,6,....
    9	9,1,9,1,...

• 4번 안에 끝자리는 이미 결정이 난다. (b가 아무리 많아도 다 계산해줄 필요가 없음)
• b를 4로 나눈 나머지를 b값으로 설정하고 만약 b가 4의 배수라서 0이 나올경우 b=4로 지정해준다.
• a의b제곱을 계산한 s가 10으로 나눈 나머지가 0이면 10을 아니라면 나머지를 answer에 추가한다.

---

import sys

T = int(sys.stdin.readline().rstrip())
answer = []
for i in range(T):
    a, b = map(int, sys.stdin.readline().split())
    b = b%4
    if b%4 ==0 :
        b = 4
    s = a**b
    if s%10 == 0:
        answer.append(10)
    else:
        answer.append(s%10)

for i in answer:
    print(i)