백준 1009번 문제 - 분산처리

---

문제 링크 : https://www.acmicpc.net/problem/1009

분산처리 문제는 어려워보이는 제목과는 달리 컴퓨터가 10대라는 점만으로 해결방법을 알 수 있는 쉬운 문제이다.

1번째 컴퓨터는 1번째 데이터, 11번째 데이터, 21번째 데이터와 같이 일의 자리가 1인 번호의 데이터를 처리하며 $a^b$개의 데이터 중 마지막 데이터는 일의 자리에 따라 처리할 컴퓨터의 번호가 결정된다.

그러나 $1\leq a < 100 , 1\leq b < 1,000,000$의 조건으로 보아 단순히 $a^b$를 계산하여 일의 자리를 찾는 것은 무리가 있어보인다.

이때 생각해야 할 것이 “일의 자리의 규칙성”이다.

예를 들어, $3^7$의 데이터에 대하여 생각해보자. $3^1=3$, $3^2=9$, $3^3=27$, $3^4=81$, $3^5=243$, $3^6=729$, $3^7=2187$로 일의자리가 3 -> 9 -> 7 -> 1의 반복이 이루어짐을 확인할 수 있다.

10 이하의 자연수에 대하여 지수함수의 일의 자리는 최대 4가지 경우의 수가 존재하며, 11 이상의 자연수는 일의 자리에 대해서만 계산하므로 10 이하의 자연수와 동일한 결과를 얻는다.

따라서 $a^b$의 일의 자리는 ${(a \mod 10)}^{b} \mod 10$이며 일의 자리의 반복 중 $b \mod 4$번째 결과와 동일한 결과를 갖는다.

#include<iostream>
using namespace std;
int arr[4];

int main(){
    int T,a,b;
    scanf("%d",&T);
    while(T--){
        scanf("%d %d",&a,&b);
        arr[0]=a%10;
        arr[1]=(arr[0]*a)%10;
        arr[2]=(arr[1]*a)%10;
        arr[3]=(arr[2]*a)%10;
        printf("%d\n",(arr[(b-1)%4]==0)?10:arr[(b-1)%4]);
    }
    return 0;
}