テトレーション
(library/number/mod/mod_tetration.hpp)

• View this file on GitHub
• Last update: 2026-01-22 14:26:48+09:00
• Include: #include "library/number/mod/mod_tetration.hpp"

テトレーション

できること

• ${a \uparrow \uparrow b} \bmod m$ を求める
  • $\uparrow \uparrow$ はテトレーション演算で、 $a^{a^{a^{a^{\ldots}}}}$ ( $a$ が $b$ 個続く) を指す

計算量

$O(\sqrt{m})$

使い方

long long ans = mod_tetration(a, b, MOD);

Depends on

• MOD 二分累乗 (library/number/mod/mod_pow.hpp)
• オイラーのφ関数 (library/number/prime/euler_phi.hpp)

Verified with

• MOD テトレーションのテスト (tests/number.mod.mod_tetration.test.cpp)

Code

#pragma once
#include "library/number/prime/euler_phi.hpp"
#include "library/number/mod/mod_pow.hpp"
template <typename T> T mod_tetration(const T &a, const T &b, const T &m) {
    if (m == 1ll) return 0ll;
    if (a == 0ll) return !(b & 1ll);
    if (b == 0ll) return 1ll;
    if (b == 1ll) return a % m;
    if (b == 2ll) return mod_pow(a, a, m);
    auto phi = euler_phi(m);
    auto tmp = mod_tetration(a, b - 1, phi);
    if (tmp == 0ll) tmp += phi;
    return mod_pow(a, tmp, m);
}

#line 2 "library/number/prime/euler_phi.hpp"
template <typename T> T euler_phi(T n) {
    T ret = n;
    for (T i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            ret -= ret / i;
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) ret -= ret / n;
    return ret;
}
#line 2 "library/number/mod/mod_pow.hpp"
long long mod_pow(long long a, long long n, long long m) {
    long long res = 1ll;
    while (n > 0) {
        if (n & 1) res = res * a % m;
        a = a * a % m;
        n >>= 1ll;
    }
    return res;
}
#line 4 "library/number/mod/mod_tetration.hpp"
template <typename T> T mod_tetration(const T &a, const T &b, const T &m) {
    if (m == 1ll) return 0ll;
    if (a == 0ll) return !(b & 1ll);
    if (b == 0ll) return 1ll;
    if (b == 1ll) return a % m;
    if (b == 2ll) return mod_pow(a, a, m);
    auto phi = euler_phi(m);
    auto tmp = mod_tetration(a, b - 1, phi);
    if (tmp == 0ll) tmp += phi;
    return mod_pow(a, tmp, m);
}

Back to top page