백준 1009번 분산처리 // JAVA

문제

분산처리

재용이는 최신 컴퓨터 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)

출력

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

---

풀이

1~10번까지 컴퓨터를 반복하는 문제이기 때문에, N(=a^b)번 데이터는 N의 1의 자릿수에 따라 어느 컴퓨터에서 처리될 지 결정된다.

 

N의 최대값이 99^(1,000,000)인데, 실제로 곱하면 오버플로우가 발생하기 때문에 다른 방법을 사용해야한다.

 

따라서, 0~9까지 수를 거듭제곱하면서 나올 수 있는 모든 1의 자릿수를 ArrayList에 저장하여 계산하였다.

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
            st = new StringTokenizer("");
        }

        String next() throws Exception {
            while (!st.hasMoreTokens()) {
                st = new StringTokenizer(br.readLine());
            }

            return st.nextToken();
        }

        int nextInt() throws Exception {
            return Integer.parseInt(next());
        }
    }

    public static void main(String[] args) throws Exception {
        Reader reader = new Reader();
        StringBuilder sb = new StringBuilder();
        int test_case = reader.nextInt();

        ArrayList<ArrayList<Integer>> list = new ArrayList<>();

        for (int i = 0; i <= 9; i++) {
            list.add(new ArrayList<Integer>());
            list.get(i).add(i);
            int last = i;

            while (true) {
                last = last * i % 10;

                if (last == i)
                    break;

                list.get(i).add(last);
            }
        }

        for (int i = 0; i < test_case; i++) {
            int a = reader.nextInt();
            int b = reader.nextInt();

            a = a % 10;

            if (a == 0) {
                sb.append("10\n");
            }

            else {
                b = (b - 1) % list.get(a).size();

                sb.append(Integer.toString(list.get(a).get(b))).append("\n");
            }
        }

        System.out.println(sb.toString());
    }
}