1009번: 분산처리

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

1009번: 분산처리

i번 데이터는 (i % 10) + 1번 컴퓨터에서 처리하고 데이터는 1번부터 a^b번 데이터까지 있으므로, 구하고자 하는 값은 (a^b) % 10이다.

또 자연수 i의 거듭제곱의 1의 자리는 항상 순환하는데, 이는 i의 1의 자리 수에 따라 결정된다.

따라서 1 <= i <= 10일 때 i의 거듭제곱의 1의 자리 수를 미리 계산해 10 * 4 크기 배열에 저장한 뒤 a % 10, b % 4를 인덱스 삼아 배열에 접근하면 빠르게 답을 출력할 수 있다.

#include <cstdio>

// e[a][b]: a^(b % 4)의 1의 자리 수
int e[10][4] = {{10, 10, 10, 10},
                { 1,  1,  1,  1},
                { 6,  2,  4,  8},
                { 1,  3,  9,  7},
                { 6,  4,  6,  4},
                { 5,  5,  5,  5},
                { 6,  6,  6,  6},
                { 1,  7,  9,  3},
                { 6,  8,  4,  2},
                { 1,  9,  1,  9}};
 
int main() {
    // T: 테스트 케이스의 수
    // a, b: a^b의 1의 자리 수를 구할 때 필요한 데이터
    int T, a, b;

    // 테스트 케이스를 입력받아 각 테스트 케이스마다
    scanf("%d", &T);
    while (T--) {
        // a와 b를 입력받는다
        scanf("%d %d", &a, &b);
        // a^b의 1의 자리 수는 (a % 10)^(b % 4)의 1의 자리 수와 같다
        printf("%d\n", e[a % 10][b % 4]);
    }

    return 0;
}