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

• View this file on GitHub
• Last update: 2022-09-11 00:53:50+09:00
• Include: #include "math/combinatorics/mod-tetration.hpp"
• Link: View error logs on GitHub Actions

概要

${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

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

Verified with

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

Code

#include "mod-pow.hpp"
#include "../number-theory/euler-phi.hpp"

/**
 * @brief Mod Tetration(テトレーション)
 * @docs docs/mod-tetration.md
 */
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/combinatorics/mod-pow.hpp"
/**
 * @brief Mod Pow(べき乗)
 * @docs docs/mod-pow.md
 */
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 1 "math/number-theory/euler-phi.hpp"
/**
 * @brief Euler's Phi(オイラーのφ関数)
 * @docs docs/euler-phi.md
 */
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 3 "math/combinatorics/mod-tetration.hpp"

/**
 * @brief Mod Tetration(テトレーション)
 * @docs docs/mod-tetration.md
 */
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);
}

Back to top page