백준_No1009_분산처리

문제

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

출력

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

---

풀이

처음 문제를 보고 풀었을 때는 다음과 같이 작성했다.

N = int(input())

for _ in range(N):
    a, b = map(int, input().split())
    res = a ** b
    print(res % 10)

결과는 시간초과로 인한 실패였다.

처음에 오류인줄 알고 다른 사람이 푼 풀이를 보니 제곱의 성질과 분산을 이용하는 문제였다.

 

제곱의 경우 맨뒷자리만 보면 규칙성을 띄고 있다.

예를들어 4의 제곱을 보면,

4^1 = 4

4^2 = 16

4^3 = 64

4^4 = 256

4, 6이 반복적으로 바뀌는것을 알 수 있다. 이것을 1부터 9까지 표로 정리하면 다음과 같다.

제곱 수	반복되는 뒷자리
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

1. 패턴이 1개
   1,5,6 은 자기자신을 그대로 출력하게끔 하고, 10일때는 0이므로 10을 출력한다.
2. 패턴이 2개
   4,9 는 자기자신 또는 제곱이기에 거듭제곱이 홀수일 경우 자기 자신을, 짝수일 경우 제곱을 출력한다.
3. 패턴이 4개
   2,3,7,8 은 4단위로 반복이 되므로 거듭제곱을 4로 나눈 나머지와 자기자신을 거듭제곱한다. 이때 거듭제곱을 4로 나눈 나머지가 0일경우 4제곱이기에 4거듭제곱을 한다.

이를 코드로 작성하면 다음과 같다.

N = int(input())

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

    if a == 0:
        print(10)
    elif a in [1, 5, 6]:
        print(a)
    elif a in [4, 9]:
        if b % 2 != 0:
            print(a)
        else:
            print(a**2 % 10)
    else:
        if b % 4 == 0:
            print((a**4) % 10)
        else:
            print(a**(b % 4) % 10)

 

[참조]

https://uni2237.tistory.com/58