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\) が求まる.