指数塔

数a的b次超幂或叫b次迭代幂（b是正整数），记作$a\uparrow\uparrow b$，是按如下方式递归定义的 $$a\uparrow\uparrow 1=a, \quad 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\times10^{12}}$。

求$1777\uparrow\uparrow1855$的最后$8$位数字。

注：容易看出$a\uparrow\uparrow b=a^{a^{\ldots^a}}$，等式右侧的$a$出现$b$次，这一形式也常被称为指数塔。

本题难度:

解答

令 $$\varphi(n)=p_1^{c_1-1}\ldots p_m^{c_m-1}(p_1-1)\ldots(p_m-1),$$ 为Euler Totient函数，其中 $$n=p_1^{c_1}\ldots p_m^{c_m},$$ 是n的质因数分解。显然只要$\gcd(a,n)=1$，那么a就是模n乘法群的元素，从而有 $$a^{\varphi(n)}=1 \pmod n.$$ 记$a_j=a\uparrow\uparrow j$，$b_k=\phi(\phi(\ldots(\phi(n))\ldots))$，其中$\phi$出现k次.

在本题中$a=1777$, $b_0=n=10^8=2^8\cdot 5^8$，容易看出 $$b_k=\begin{cases}2^{8+k}\cdot 5^{8-k} & k\le 8, \\ 2^{24-k} & k\le24, \end{cases}$$ 因此$\gcd(a,b_k)=1$总是成立，因此有 $$a_{1855} \bmod b_0=a^{a_{1854}\bmod b_1} \mod b_0=\ldots,$$ 递归求解即得结果$95962097$。

注：本题需要具备本科程度的《抽象代数》知识。

def tower(a,k,x,y):
  if x==y==0:
      return 0
  elif k==0:
      return 1
  elif y>0:
      return pow(a,tower(a,k-1,x+1,y-1),(1 << x)*(5**y))
  else:
      return pow(a,tower(a,k-1,x-1,0),(1 << x)*(5**y))

print tower(1777,1855,8,8)