1009. 분산처리

사실 어려운 문제는 아니다. 

정리하는 이유는 바보같이 틀려가지고.... ㅋㅋ

 

처음에 문제만 보고 음~ 쉽군~ 하면서 그냥 a**b를 계산했고 당연히 시간초과가 떴음

당연함 제곱을 바로 해주면 b의 범위도 크고 수의 크기도 너무 커지기 때문! 

 

그래서 제곱할 때 일의 자리 끼리의 규칙이 있다는 걸 사용하기로 했다.

2부터 9까지 값을 거듭제곱 했을 때의 일의자리 패턴이 4개 단위로 반복되거나, 2개 단위로 반복되거나, 1개 단위로 반복되는 것을 알아낼 수 있었다. 

그럼 숫자를 다섯제곱 했을 때의 일의 자릿수와 일제곱 했을 때의 일의 자릿수가 같을 수 밖에 없다는 소리다.

여섯제곱 했을 때의 일의 자릿수와 제곱 했을 때의 일의 자릿수가 같을 수 밖에 없다는 소리다.

 

위의 방법을 사용한 코드는 이렇다.

import sys
input = sys.stdin.readline

n = int(input())
for _ in range(n) :
    a, b = map(int, input().split())
    a = a%10
    b = b%4
    if b == 0 : 
        b = 4
    com = (a**b)%10
    print(com if com != 0 else 10)

 

 

 

각 숫자들 간의 패턴을 미리 저장해놓고 꺼내서 사용하는 방식으로 코드를 짤 수도 있다.

import sys
input = sys.stdin.readline

last_digit = [[i] for i in range(10)]
size = []

for i in range(10) :
    temp = i
    while i != (temp*i)%10 :
        temp *= i
        last_digit[i].append(temp%10)
    size.append(len(last_digit[i]))

n = int(input())
for _ in range(n) :
    a, b = map(int, input().split())
    a = a%10
    b = b%size[a]-1
    print(10 if a == 0 else last_digit[a][b])