[백준] 1009 분산처리 (C++)

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

1009번: 분산처리

문제

재용이는 최신 컴퓨터 10대를 가지고 있다. 어느 날 재용이는 많은 데이터를 처리해야 될 일이 생겨서 각 컴퓨터에 1번부터 10번까지의 번호를 부여하고, 10대의 컴퓨터가 다음과 같은 방법으로 데이터들을 처리하기로 하였다.

1번 데이터는 1번 컴퓨터, 2번 데이터는 2번 컴퓨터, 3번 데이터는 3번 컴퓨터, ... ,

10번 데이터는 10번 컴퓨터, 11번 데이터는 1번 컴퓨터, 12번 데이터는 2번 컴퓨터, ...

총 데이터의 개수는 항상 a^b개의 형태로 주어진다. 재용이는 문득 마지막 데이터가 처리될 컴퓨터의 번호가 궁금해졌다. 이를 수행해주는 프로그램을 작성하라.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a < 100, 1 ≤ b < 1,000,000)

 

출력

각 테스트 케이스에 대해 마지막 데이터가 처리되는 컴퓨터의 번호를 출력한다.

---

풀이

문제에 따르면 데이터가 처리될 컴퓨터의 번호는 데이터의 번호를 10으로 나눈 값의 나머지이다. 즉 데이터의 번호에서 마지막 일의 자리 수가 곧 데이터가 처리되는 컴퓨터의 번호이다. 

그런데 데이터의 최대 개수는 매우 많다. 99^999999 를 직접 계산할 수는 없다. 하지만 일의 자리 수는 알아낼 수 있다.

 

a^b는 a를 b번 곱했다는 뜻으로 a * a * a ..... * a 꼴이다. 이 때 a의 값이 2, b의 값이 999라고 가정하자. 2를 반복하여 곱하면 2, 4, 8, 16, 32, 64, 128, 256, 512 ... 와 같이 수들이 나열되는데 일의 자리 수에 주목하자. 일의 자리 수는 2, 4, 8, 6, 2, 4, 8, 6, 2... 와 같이 [2, 4, 8, 6] 4개의 수가 반복하여 등장하는 것을 알 수 있다. 따라서 2^999의 일의 자리 수는 [2, 4, 8, 6] 에서 999를 4로 나눈 나머지 3번째 수 8임을 알 수 있다. 

a의 값이 3일 때도 마찬가지이다. 3을 반복하여 곱하면 3, 9, 27, 81, 243, 729, 2187, 6561, 19683... 와 같이 수들이 나열되고 일의 자리 수를 살펴보면 [3, 9, 7, 1] 4개의 수가 반복하여 등장하는 것을 확인할 수 있다. 

 

따라서 우리는 a를 4번 곱하며 반복되는 4개의 수를 구한 뒤, b를 4로 나눈 나머지를 구하여 일의 자리 수를 구할 수 있다.

 

코드

#include <iostream>
using namespace std;

int main() {
    int T;
    cin >> T;

    for (int i = 0; i < T; i++){
        int a, b;
        cin >> a >> b;

        int aArray[4];  // 반복되는 4개의 수 저장
        int lastNumA = a % 10;
        for (int i = 0; i < 4; i++){
            aArray[i] = lastNumA;
            lastNumA = lastNumA * a % 10;
        }

        int ans = aArray[(b-1)%4];

        if(ans){ // ans값이 0이 아닐 때
            cout << ans << endl;
        }
        else{ // ans 값이 0일 때
            cout << 10 << endl;
        }

    }

}