[Math] 백준 1009번 : 분산처리 (다시 보기)

[jeongabae]

브론즈2

브론즈2라고 헹하면서 풀었는데 시간초과 났던..ㅎㅋ 규칙을 찾아야했던 문제였다.

시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 -- | -- | -- | -- | -- | -- 1 초 | 128 MB | 73424 | 17214 | 13662 | 24.318%

문제

재용이는 최신 컴퓨터 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)

출력

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

예제 입력 1 복사

5
1 6
3 7
6 2
7 100
9 635

예제 출력 1 복사

1
7
6
1
9

출처

• 문제를 만든 사람: hellodj
• 데이터를 추가한 사람: kjiwhan0120, sait2000

알고리즘 분류

• 수학
• 구현

제출한 코드 1 : 시간초과

# 당연하게 b가 너무 커서 시간초과 날 수 밖에..
T = int(input())
for _ in range(T):
    a,b=map(int,input().split())
    ans = a**b%10
    print(ans if ans else 10)

제출한 코드2 : 정답

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    a,b = map(int,input().split())
    aa=a%10

    if aa == 0: # 패턴 1
        print(10)
    elif aa in [1,5,6]:
        print(aa)
    elif aa in [4,9]: # 패턴2
        bb=b%2
        print(aa*aa%10 if bb==0 else aa)

    else: #패턴 4
        bb=b%4
        print(aa**4%10 if bb==0 else aa**bb%10)

https://uni2237.tistory.com/58 이 분 풀이를 참고 했다. 수	거듭제곱
1	1
2	2, 4, 6, 8
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
10	0

패턴이 하나 -> 1,5,6은 자기자신을 그대로 출력하게끔 하고, 10일때는 0이므로 10(컴퓨터번호니까) 출력하도록 한다.

패턴이 2개 ->이번엔 b도 10으로 나눈 나머지를 구하고 , 나머지가 0이면 a를 그대로 출력, 아니라면 a * a 의 일의자리를 출력.

패턴이 4개 -> b를 10으로 나눈 나머지를 bb라고 하고, 나머지가 0이면 a를 그대로 출력, 아니라면 a를 bb만큼 거듭제곱한것의 나머지를 출력하도록 한다.