[BOJ/C++] 백준 1009 분산처리

문제

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

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

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

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

입력

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

출력

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

 

---

 

 1부터 10까지 마지막 자릿수에 따라 번호가 정해지기 때문에 굳이 모든 계산을 할 필요는 없다. a^b가 아무리 큰 수라도, 예를 들어 2,097,152 이런 숫자라 해도 일의 자리만 보면 2번 컴퓨터로 처리될 것을 알 수 있기 때문이다. 처음에는 pow 함수로 직접 제곱해봤으나, b의 범위가 너무 커서 자꾸만 오버플로우가 발생했다. 역시나 직접 제곱해서 푸는 문제는 아닌 것 같아 다른 방법을 모색해보았다. 

 

 일단 일의 자리 숫자만 알면 된다는 사실에 입각해 제곱할 때마다 10으로 나눈 나머지를 구하는 방법을 생각해봤다. 7을 100번 제곱한다고 하면 7*7 = 49, 49를 10으로 나눈 나머지인 9*7 = 63, 3*7=21 이런 식으로 일의 자리만 계산해도 된다는 것을 알 수 있다. 하지만 b의 범위가 굉장히 크기 때문에 반복문을 돌리는 데 시간이 오래 걸리고 비효율적이다. 대신 일의 자리가 반복된다는 특징을 이용해 배열에 저장하기로 했다.

 

1~10까지 각각의 수를 제곱했을 때 반복되는 일의 자릿수는 다음과 같다. 

1	1	1	1	1	1	1	1
2	4	8	6	2	4	8	6
3	9	7	1	3	9	7	1
4	6	4	6	4	6	4	6
5	5	5	5	5	5	5	5
6	6	6	6	6	6	6	6
7	9	3	1	7	9	3	1
8	4	2	6	8	4	2	6
9	1	9	1	9	1	9	1
0	0	0	0	0	0	0	0

 최대 4개까지 반복되므로 4행 10열 크기의 2차원 배열을 만들어 나머지 수를 저장할 것이다. 인덱스가 0부터 시작한다는 점을 고려하여 10,1, · · ·,9 순으로 저장했다. 4단위로 반복되므로, 마찬가지로 인덱스를 고려해 b-1을 4로 나눈 나머지 순서가 해당 제곱수의 컴퓨터 번호가 될 것이다.

 

 예를 들어 a가 3, b가 9라고 해보자. 즉, 3의 9제곱은 일의 자리 수가 4개씩 반복되어 3,9,7,1,3,9,7,1,3 → 3이 된다. 9를 4로 나눈 나머지는 1이다. 배열의 첫번째 칸에 들어있는 것이다. 인덱스로는 0이므로 1을 빼주기만 하면 된다. a의 범위는 1부터 100인데, 1부터 10까지 10번씩 반복된다고 생각하면 된다. 3, 13, 23, 33의 제곱수도 일의 자리 숫자가 반복되는 건 같다. 그래서 10의 나머지를 구한 수를 인덱스로 넣어주는데, 10 단위는 일의 자리가 0이므로 0번째에 들어가도록 배열의 첫번째 행에 저장했다.

 

[코드]

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    int t;
    cin >> t;
    int arr[10][4] = {{10,10,10,10},{1,1,1,1},{2,4,8,6},{3,9,7,1},{4,6,4,6},
    {5,5,5,5},{6,6,6,6},{7,9,3,1},{8,4,2,6},{9,1,9,1}};
    for(int i=0; i<t; i++){
        int a, b = 0;
        int num = 0;
        cin >> a >> b;
        num = arr[a%10][(b-1)%4];
        cout << num << "\n";
    }
    return 0;
}

a와 b를 입력받아 배열에서 찾은 컴퓨터 번호 num을 출력한다. 참고로 (b-1)%4나 (b%4)-1이나 계산한 값은 같다.