백준 1009 : 분산처리

https://www.acmicpc.net/problem/1009

1009번: 분산처리

 

1~10의 제곱 수들의 일의 자릿수들을 나열해보면 다음과 같습니다.

1 : [1, 1, 1, 1, ...]

2 : [2, 4, 8, 6, ...]

3 : [3, 9, 7, 1, ...]

4 : [4, 6, 4, 6, ...]

5 : [5, 5, 5, 5, ...]

6 : [6, 6, 6, 6, ...]

7 : [7, 9, 3, 1, ...]

8 : [8, 4, 2, 6, ...]

9 : [9, 1, 9, 1, ...]

10 : [0, 0, 0, 0, ...]

패턴을 살펴보면, 아무리 많아봤자 최대 네 개의 수만 반복되고 있습니다.

즉, 2^1이나 2^201이나 일의 자릿수는 2로 동일합니다.

따라서 b를 4로 나눈 나머지 값의 횟수(0 이면 4회)만큼만 제곱해서 확인하면 되므로,

최대 네 번만 검사하면 마지막 데이터가 처리되는 컴퓨터의 번호를 알 수 있습니다.

 

#include <cstdio>
int n, a, b, t;
int main() {
	scanf("%d", &n);
	while (n--) {
		scanf("%d %d", &a, &b);
		b %= 4;
		b = b == 0 ? 4 : b;
		t = a % 10;
		while (--b) t = t * a % 10;
		printf("%d\n", t == 0 ? 10 : t);
	}
}