test/verify/yosupo-tetration-mod.test.cpp

• View this file on GitHub
• Last update: 2026-08-10 14:29:01+00:00
• Problem: https://judge.yosupo.jp/problem/tetration_mod

Depends on

• Mod Pow (べき乗) (math/combinatorics/mod-pow.hpp)
• Mod Tetration (テトレーション) (math/combinatorics/mod-tetration.hpp)
• Euler's Phi (オイラーのφ関数) (math/number-theory/euler-phi.hpp)

Code

// clang-format off
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/tetration_mod
// clang-format on

#include <iostream>

#include "../../math/combinatorics/mod-tetration.hpp"

using namespace std;

int main() {
  int T;
  cin >> T;
  while (T--) {
    int a, b, m;
    cin >> a >> b >> m;
    cout << mod_tetration<long long>(a, b, m) % m << "\n";
  }
}

#line 1 "test/verify/yosupo-tetration-mod.test.cpp"
// clang-format off
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/tetration_mod
// clang-format on

#include <iostream>

#line 2 "math/combinatorics/mod-tetration.hpp"

#line 1 "math/number-theory/euler-phi.hpp"
/**
 * @brief Euler's Phi(オイラーのφ関数)
 *
 */
#line 6 "math/number-theory/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 "math/combinatorics/mod-pow.hpp"

#include <cstdint>

/**
 * @brief Mod Pow(べき乗)
 *
 */
template <typename T>
T mod_pow(T x, std::int64_t n, const T& p) {
  T ret = 1;
  while (n > 0) {
    if (n & 1) (ret *= x) %= p;
    (x *= x) %= p;
    n >>= 1;
  }
  return ret % p;
}
#line 5 "math/combinatorics/mod-tetration.hpp"

/**
 * @brief Mod Tetration(テトレーション)
 *
 */
template <typename T>
T mod_tetration(const T& a, const T& b, const T& m) {
  if (m == 1) return 0;
  if (a == 0) return !(b & 1);
  if (b == 0) return 1;
  if (b == 1) return a % m;
  if (b == 2) return mod_pow(a, a, m);
  auto phi = euler_phi(m);
  auto tmp = mod_tetration(a, b - 1, phi);
  if (tmp == 0) tmp += phi;
  return mod_pow(a, tmp, m);
}
#line 8 "test/verify/yosupo-tetration-mod.test.cpp"

using namespace std;

int main() {
  int T;
  cin >> T;
  while (T--) {
    int a, b, m;
    cin >> a >> b >> m;
    cout << mod_tetration<long long>(a, b, m) % m << "\n";
  }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	2_3_32_00	AC	2 ms	4 MB
g++	example_00	AC	2 ms	4 MB
g++	example_01	AC	1 ms	4 MB
g++	max_00	AC	20 ms	4 MB
g++	max_01	AC	17 ms	4 MB
g++	max_02	AC	17 ms	4 MB
g++	max_1000000000_00	AC	7 ms	4 MB
g++	max_1000000000_01	AC	7 ms	4 MB
g++	max_1000000000_02	AC	8 ms	4 MB
g++	max_998244353_00	AC	87 ms	4 MB
g++	max_998244353_01	AC	90 ms	4 MB
g++	max_998244353_02	AC	94 ms	4 MB
g++	random_00	AC	17 ms	4 MB
g++	random_01	AC	6 ms	4 MB
g++	random_02	AC	4 ms	4 MB
g++	random_03	AC	6 ms	4 MB
g++	random_04	AC	13 ms	4 MB
g++	small_00	AC	3 ms	4 MB
g++	small_ab_00	AC	13 ms	4 MB
clang++	2_3_32_00	AC	2 ms	4 MB
clang++	example_00	AC	2 ms	4 MB
clang++	example_01	AC	1 ms	4 MB
clang++	max_00	AC	13 ms	4 MB
clang++	max_01	AC	15 ms	4 MB
clang++	max_02	AC	13 ms	4 MB
clang++	max_1000000000_00	AC	9 ms	4 MB
clang++	max_1000000000_01	AC	9 ms	4 MB
clang++	max_1000000000_02	AC	9 ms	4 MB
clang++	max_998244353_00	AC	56 ms	4 MB
clang++	max_998244353_01	AC	55 ms	4 MB
clang++	max_998244353_02	AC	57 ms	4 MB
clang++	random_00	AC	9 ms	4 MB
clang++	random_01	AC	4 ms	4 MB
clang++	random_02	AC	3 ms	4 MB
clang++	random_03	AC	4 ms	4 MB
clang++	random_04	AC	7 ms	4 MB
clang++	small_00	AC	2 ms	4 MB
clang++	small_ab_00	AC	7 ms	4 MB

Back to top page