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)