[백준] 1009번 : 분산처리 (파이썬)

문제

나의 첫번째 답안(시간초과)

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

이렇게 풀면 a**b연산을 하는 과정에서 시간 복잡도가 증가한다.

나의 최종 답안

import sys 
input = sys.stdin.readline

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

    if base==0:#1의 자리가 0인 경우(10의 배수)
        print(10)
    elif base==1 or base==5 or base==6:#1,5,6인경우
        print(base)
    elif base==4 or base==9:#4,9 : 값을 그대로 가지거나, 제곱의 나머지
        if b%2==0:
            print((base**2)%10)
        else:
            print(base)
    else:#2,3,7,8
        if b%4==0:
            print(base**4%10)#4로 나눈 나머지를 바로 쓰면 오류 남
        else:
            print(base**(b%4)%10)   

접근 방법

• 총 10대의 컴퓨터가 동작하므로 10을 한바퀴 돌아도 1의 자리 값이 일정하다.

0	10
1	1
2	2 4 8 6
3	9 7 1
4	4 6
5	5
6	6
7	9 3 1
8	8 4 2 6
9	9 1

다음과 같다.

• 여기서 1의 자리 0은 10의 배수와 동일하다.
  1, 5, 6은 본인을 그대로 가진다.
  4와 9는 본인과 본인을 제곱한 수를 10으로 나눈 나머지의 값을 갖는다.(4^2=16 16%10=6)
  마지막으로 2,3,7,8은 지수를 10으로 나눈 나머지를 계산하고, 나머지가 0이면 그대로 출력, 아니라면 base를 지수만큼 제곱한 값의 나머지를 계산해주면 된다.