No.181

$$\begin{align} B(a, n) &= a \uparrow\uparrow n = a^{B(a, n-1)} \\ C(a, n, m) &= B(a, n) \bmod m = a^{B(a, n-1)} \bmod m \end{align}$$

とおく. ここで $\{a^k \bmod m \mid k=1,2,\dots\}$ は余りの個数が $m$ 個以下なので, $i$ 番目から周期 $j$ で必ずループする. そして $i \lt m, j \lt m$ となる.

$k \leq m$ のときは愚直に計算する.

$k \gt m$ のときは,

$$a^k \bmod m = a^{m + ((k - m) \bmod j)} \bmod m$$

となるので,

$$\begin{align} C(a, n, m) &= a^{B(a, n - 1)} \bmod m \\ &= a^m a^{(B(a, n - 1) - m) \bmod j} \\ &= a^m a^{(C(a, n - 1, j) - (m \bmod j))} \end{align}$$

となる. これを再帰的に計算すればいい.

なお, $B(a, n-1) \gt m$ かどうかの判定だが, 以下のように行う.

• $B(2, 4) = 2^{16} \gt m$ であるので, $n-1 \geq 4$ の場合は超える.
• $B(3, 3) = 3^{27} \gt m$ であるので, $n-1 = 3, a \geq 3$ の場合は超える.
• $B(5, 2) = 3125 \gt m$ であるので, $n-1 = 2, a \geq 5$ の場合は超える.
• その他の場合は愚直に計算する.