我有一道奥林匹克竞赛题中的数学题，我正在尝试用代码实现它。问题是，我无法弄清楚这个问题的逻辑。
问题是，
9^(9^(9^(9^...... 1001 次....)))。答案的最后 5 位数字是多少？
如果有人能告诉我如何做到这一点，我会很高兴。请记住，由于我需要在代码中实现它，因此采用较少步骤并因此在复杂性方面更优化的解决方案对我来说是有利的。
但是，如果您有任何方法可以找到正确的解决方案，我也想知道这一点，因为我还没有弄清楚这个问题。
最佳答案
其他一些答案似乎计算出了 9^1001。这不是提出的问题。这对于奥林匹克竞赛问题来说太简单了。
定义 T(a,n) 使得 T(a,1) = a，并且 T(a,n) = a^T(a,n-1)。这叫做 tetration .该问题要求 T(9,1001) mod 100,000。
要解决实际问题，使用哪个模数并不明显。 T(a,n) mod m 并不总是 T(a,n mod m) mod m。例如，T(2,3) = 2^2^2 = 2^4 = 16。T(2,4) = 2^16 = 65536。模 10，您不能只计算 T(2,3) mod 10 = 6 然后 2^6 mod 10 = 64 mod 10 = 4。T(2,4)=65536 最后一位是 6，不是 4。
但是，您可以算出 9^2500 = 1 mod 100000，所以 9^100000 = 1 mod 100000 也是。 (根据中国剩余定理，您可以分析 9 mod 2^5 和 5^5 的幂。)因此，您只需跟踪 T(9,n) mod 2500 或 100000 的值即可确定 T(9, 1001) mod 100000。计算 t = T(9,1000) mod 2500，然后计算 powermod(9,t,100000)。
事实上，将 n 映射到 9^n mod 100000 的函数会迅速稳定到固定点 45289。9^9 mod 2500 是 489，9^489 mod 2500 是 2289，9^2289 mod 2500 是 289 ，而 9^289 mod 2500 又是 289。因为 9^289 mod 100000 是 45289，所以 T(9,4), T(9,5), ..., T(9,1001) 都以 45289 结尾。
编辑:让我充实 Egor Skriptunoff 的评论。 9 模 10^5 循环的幂，周期除以 phi(10^5)=40000，其中 phi 是 Euler Totient function .所以，我们只需要确定T(9,1000) mod 40000。周期除以phi(40000) =16000的9 mod 40000循环的幂，所以我们只需要找到T(9,999) mod 16000等。因为phi迭代10^5 的 15 次是 1，我们知道 9 mod phi^15(10^5) 的任何幂的值，因此 T(9,16) = T(9,n) mod 10^5 对于任何更大的n.
关于performance - 代码的递归求幂，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25458742/