No.747
\(N^K \ \% \ 6\) を求めれば数字が求まる. これは \((N \ \% \ 6)^K \ \% \ 6\) で計算できる.
まずは \(N \ \% \ 6\) を考える. これは \(N \ \% \ 2, N \ \% \ 3\) を求めればいい. 2で割った余りは下一桁を見れば分かるし, 3で割った余りはすべての数字を足して3で割った余りである.
N%2 | N%3 | N%6 |
---|---|---|
0 | 0 | 0 |
0 | 1 | 4 |
0 | 2 | 2 |
1 | 0 | 3 |
1 | 1 | 1 |
1 | 2 | 5 |
次に \((N \ \% \ 6)^K \ \% \ 6\) であるが, これは \(K\) を順に計算していくと以下のように周期2でループする.
N%6 | 1 | 2 | 3 | 4 |
---|---|---|---|---|
0 | 0 | 0 | 0 | 0 |
1 | 1 | 1 | 1 | 1 |
2 | 4 | 2 | 4 | 2 |
3 | 3 | 3 | 3 | 3 |
4 | 4 | 4 | 4 | 4 |
5 | 1 | 5 | 1 | 5 |
よって \(K \ \% \ 2\) が分かれば \((N \ \% \ 6)^K \ \% \ 6\) が求まる.