Mod Tetration(テトレーション) (math/combinatorics/mod-tetration.hpp)

View this file on GitHub
View document part on GitHub
Last update: 2024-04-27 01:27:28+09:00
Include: #include "math/combinatorics/mod-tetration.hpp"

概要

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

使い方

mod_tetration(a, b, m): ${a \uparrow \uparrow b} \bmod m$ を返す.

計算量

$O(\sqrt m)$

Depends on

Verified with

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

Code

#include "../number-theory/euler-phi.hpp"
#include "mod-pow.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 1 "math/number-theory/euler-phi.hpp"
/**
 * @brief Euler's Phi(オイラーのφ関数)
 *
 */
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 1 "math/combinatorics/mod-pow.hpp"
/**
 * @brief Mod Pow(べき乗)
 *
 */
template <typename T>
T mod_pow(T x, 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 3 "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);
}