数学技巧

扩展欧拉定理 & 无穷幂塔

设 \(f(x,a,0)=a,f(x,a,k)=x^{f(x,a,k-1)}(k>0)\)，并设 \(g(x,a,m) = \lim_{k \to + \infin} (f(x,a,k) \bmod m)\)。

有

\[ g(x,a,1)=0 \\ g(x,a,m)=x^{g(x,a,\phi(m))+\phi(m)} \bmod m \]

容易发现 \(g\) 的值与 \(a\) 无关，故舍去。

发现我们找到了 \(x^{x^{x^{\cdots}}}\) 在 \(\bmod m\) 意义下的值，于是可以解决 这道题。

考虑回到 \(f\) 的计算，有

\[ \left\{ \begin{aligned} & f(x,a,k) \equiv x^{f(x,a,k-1) \bmod \phi(m) + \phi(m)} \pmod m , &f(x,a,k-1) \ge \phi(m) \\ & f(x,a,k) \equiv x^{f(x,a,k-1)} \pmod m, &f(x,a,k-1) \lt \phi(m) \\ \end{aligned} \right. \]

发现当 \(k\) 超过 \(O(\log m)\) 后会递归到求 \(f(x,a,k) \bmod 1 = 0\) 的情况，于是 \(a\) 就没用了，可以解决 这道题。

实际上可以继续拓展，主要思想是递归计算指数，同时要注意判断 \(f\) 的值是否足够大，参考 例题。