Project Euler 188

题目

The hyperexponentiation of a number

The hyperexponentiation or tetration of a number a by a positive integer b, denoted by \(a\uparrow\uparrow b\) or \(^ba\), is recursively defined by:

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

Thus we have e.g. \(3\uparrow\uparrow2 = 3^3 = 27\), hence \(3\uparrow\uparrow3 = 3^{27} = 7625597484987\) and \(3\uparrow\uparrow4\) is roughly \(10^{3.6383346400240996*10^{12}}\).

Find the last \(8\) digits of \(1777\uparrow\uparrow1855\).

欧拉降幂公式

欧拉降幂公式，用于高效计算\(a^b\% m\)的值（尤其\(b\)很大时）：

\[ a^b\equiv \left \{\begin{aligned} &a^{b\% \varphi(m)} & & \text{if}\quad \gcd(a,m)=1 \\ &a^b & & \text{else if}\quad b<\varphi(m) &\pmod m\\ &a^{b\%\varphi(m)+\varphi(m)} & & \text{else} \end{aligned}\right. \]

其中\(\varphi\)为欧拉函数。

解决方案

根据式子的定义，通过欧拉降幂公式直接递归计算指数，再计算出式子的值本身。可以知道，递归的层数很低。

代码

from tools import phi
from math import log

N = 1777
M = 1855
mod = 10 ** 8


def dfs(a: int, f: int, mod: int):
    if f <= 1:
        return pow(a, f, mod), False
    elif mod == 1:
        return 0, True
    else:
        ph = phi(mod)
        val, flag = dfs(a, f - 1, ph)
        if flag or val * log(a) >= log(mod):
            return pow(a, val + ph, mod), True
        else:
            return pow(a, val, mod), False


ans = "{:08}".format(dfs(N, M, mod)[0])
print(ans)