問題: BOJ 1009 — 分散処理 · English · 한국어
各テストケースについて、a^b の一の位、つまり 10 で割った余りを二分累乗法で計算します。繰り返し周期を別途探す必要はなく、底が 10 で割り切れる場合も正しく処理できます。得られた余りはコンピューターの番号を表します。ただし余りが 0 の場合は 10 番を意味します（コンピューターの番号は 1 から 10 です）。
プログラムはテストケース数を読み取り、それぞれの (a, b) の組を独立して処理します。各ケースの計算量は O(log b) です。
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
int testCases = Integer.parseInt(input.readLine().trim());
StringBuilder output = new StringBuilder();
for (int test = 0; test < testCases; test++) {
String[] values = input.readLine().trim().split("\\s+");
int a = Integer.parseInt(values[0]);
long b = Long.parseLong(values[1]);
int lastDigit = (int) powerModuloTen(a, b);
output.append(lastDigit == 0 ? 10 : lastDigit).append('\n');
}
System.out.print(output);
}
static long powerModuloTen(int base, long exponent) {
long result = 1;
long factor = base % 10;
while (exponent > 0) {
if ((exponent & 1) != 0) result = (result * factor) % 10;
factor = (factor * factor) % 10;
exponent >>= 1;
}
return result;
}
}