Yukicoder No.167 N^M mod 10

,

http://yukicoder.me/problems/no/167

No.467 隠されていたゲームのeditorialで紹介されてためぐるちゃんの解説が面白かったので解いた。 CTFの暗号問っぽさをすこし感じる。

solution

modにより発生する周期性。$O(1)$。

>>> for k in range(10): print(k, [ (k**i)%10 for i in range(20) ])
... 
0 [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
1 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
2 [1, 2, 4, 8, 6, 2, 4, 8, 6, 2, 4, 8, 6, 2, 4, 8, 6, 2, 4, 8]
3 [1, 3, 9, 7, 1, 3, 9, 7, 1, 3, 9, 7, 1, 3, 9, 7, 1, 3, 9, 7]
4 [1, 4, 6, 4, 6, 4, 6, 4, 6, 4, 6, 4, 6, 4, 6, 4, 6, 4, 6, 4]
5 [1, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5]
6 [1, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6]
7 [1, 7, 9, 3, 1, 7, 9, 3, 1, 7, 9, 3, 1, 7, 9, 3, 1, 7, 9, 3]
8 [1, 8, 4, 2, 6, 8, 4, 2, 6, 8, 4, 2, 6, 8, 4, 2, 6, 8, 4, 2]
9 [1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9]

implementation

#!/usr/bin/env python3
n = int(input())
m = int(input())
print(pow(n % 10, m % 4 + 4, 10) if m else 1)