188. 数的超幂(The hyperexponentiation of a number)

数\(a\)的正整数\(b\)次超幂或迭代幂次记作\(a\uparrow\uparrow b\)，并按照如下方式递归定义：

$$ a\uparrow\uparrow1=a,a\uparrow\uparrow(k+1)=a^{(a\uparrow\uparrow k)} $$

举例来说\(3\uparrow\uparrow2=3^3=27\)，因此\(3\uparrow\uparrow3=3^{27}=7625597484987\)，而\(3\uparrow\uparrow4\)约为\(10^{3.6383346400240996*10^{12}}\)，求\(1777\uparrow\uparrow1855\)的最后八位数字。

分析：根据题意要示\(1777\uparrow\uparrow1855\)的最后八位数字，即求\(1777\uparrow\uparrow1855\ mod\ 10^8\)。根据题目中的示例，迭代幂次是一种增长非常快的运算，所以\(1777\uparrow\uparrow1855\)会是一个天文数字，所以我们决不能通过求出它的值之后再对它取余，必须使用其它的办法。我们知道计算一个幂的余数可以使用快速幂模算法，通过这种方法我们可以在不求幂的情况下快速计算出幂模，而在python中我们使用自带的\(pow()\)函数即可以实现这种算法。

下面我们再来看迭代幂次的定义，我们将\((a\uparrow\uparrow k)\ \%\ m\)记为一个函数\(H(a,k,m)\)，则题目要求的答案即为\(H(1777,1855,10^8)\)。已知\(a=1777\)是一个质数，则有\(gcd(a,m)=1\)，则根据欧拉定理,我们可以简化大指数的运算，即有：

同时容易得到边界条件为\(H(a,1,m)=a\%m\)以及\(H(a,k,2)=1\)(因为题目中\(a\)是一个奇数，而奇数自乘后只能为奇数，所以模二余一)，于是我们得到一个递归方程：

有了上面的递归方程，我们可以很容易的得到答案。可惜的是，在\(python\)中，题目要求的数据量导致求解时超出最大递归深度，无法求解，所以必须改用递推的方法。

使用在这篇论文末尾介绍的思路，我们先求出\(m,\varphi(m),\varphi(\varphi(m)),\cdots\)这样的序列直到其为二，我们把这个序列倒转，则值分别为\(\varphi_1=2,\varphi_2,\varphi_3,\cdots,\varphi_i=m\)，则有：

使用上述递推关系，当\(\varphi_i=10^8\)时，我们就都求得了题目的解。代码如下：

# time cost = 31.9 µs ± 78.6 ns

from sympy.ntheory import totient

def main(b=1777,e=1855,m=10**8):
    res,phis = 1,[m]
    while m != 1:
        m = totient(m)
        phis.append(m)
    for phi in reversed(phis):
        res = pow(b,res,phi)
    return res