분산처리
예시 설명을 보면 a = 10일때, 10개의 컴퓨터는 1번, 2번, ..., 10번, 1번, 2번, ... 이렇게 순서가 매겨진다. b = 5면 5번 컴퓨터가, b = 10이면 10번 컴퓨터가, b = 11이면 1번 컴퓨터가 마지막으로 작업한다.
a^b % 10과 연관이 깊다.
하지만 a^b를 계산하는데 O(b)이고 T개의 테스트케이스가 있으므로 O(Tb)의 시간복잡도가 소요된다. 문제에 T는 몇개가 들어오는지 모르지만 이렇게 해도 시간초과가 뜰 것 같지는 않다.
하지만 거듭제곱의 특징을 이용하면 빠르게 계산할 수 있다.
2의 거듭제곱은 2, 4, 8, 6이 반복된다. 즉, (2^10)%10을 계산할 때 1024%10이 아니라, 지수가 10이고, 주기가 4이므로 2번째 숫자인 4를 바로 알 수 있다는 것이다.
3의 거듭제곱은 3, 9, 7, 1
4의 거듭제곱은 4, 6
5와 6의 거듭제곱은 각각 5, 6
7의 거듭제곱은 7, 9, 3, 1
8의 거듭제곱은 8, 4, 2, 6
9의 거듭제곱은 9, 1
10의 거듭제곱은 0
아래는 파이썬 코드이고 C++은 생략한다.
T = int(input())
L2 = [6, 2, 4, 8]
L3 = [1, 3, 9, 7]
L4 = [6, 4]
L7 = [1,7, 9, 3]
L8 = [6, 8, 4, 2]
L9 = [1, 9]
for _ in range(T):
a, b = map(int, input().split())
a = a % 10
ans = 0
if a == 0:
ans = 10
elif a == 1:
ans = 1
elif a == 2:
ans = L2[b%4]
elif a == 3:
ans = L3[b%4]
elif a == 4:
ans = L4[b%2]
elif a == 5:
ans = 5
elif a == 6:
ans = 6
elif a == 7:
ans = L7[b%4]
elif a == 8:
ans = L8[b%4]
else:
ans = L9[b%2]
print(ans)참고할 만한 수학문제
(가) a(2) = x라 하면
a(1) = 7, a(2) = x, a(3) = 3, a(4) = x - 4, a(5) = -1, a(6) = x - 8
(나) 에서 주기가 6인 수열임을 알 수 있다.
따라서 a(1)~a(50)의 합은 주기가 8번 들어가 있으므로
8*[a(1)+a(2)+a(3)+a(4)+a(5)+a(6)] + a(1)+a(2) = 258
x = 11
