【2021牛客寒假算法基础集训营1】H 幂塔个位数的计算（欧拉降幂）

虽然可以找规律，但是太难了Orz蒟蒻只能选择欧拉降幂。
我们先来看下扩展欧拉定理：

截自oiwiki

欧拉降幂就是用第三条式子来降低幂次，方便计算的。
PS：这里为什么不会出现第二条式子的情况？我大概算了下，a取1的情况我们会特判掉，a取2以上大概就不会发现第二条式子的情况了。所以，不需要考虑第二条式子。
UPD:保险起见，我还是加了判断是否使用第二条式子的部分。
例如，我们按照样例1：
我们要求的其实就是：

而如果层数再多:任何数mod 1都为0，直接返回0即可。这可能也是存在规律的依据。
大数，写python呀！

from math import log
def phi(x):
    if x == 10:
        return 4
    if x == 4:
        return 2
    if x == 2:
        return 1
    if x == 1:
        return 1


def cal(a, n, mod):
    if (mod == 1):
        return 1
    if n == 1:
        return a % mod + mod
    save=cal(a, n - 1, phi(mod))
    res=pow(a, cal(a, n - 1, phi(mod)), mod)
    if(save*log(a)<log(mod)):
        return res
    return res + mod


a = int(input())
n = int(input())
if (n == 1):
    print(a % 10)
else:
    print(pow(a, cal(a, n - 1, phi(10)), 10))