This documentation is automatically generated by competitive-verifier/competitive-verifier
#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$ を返す.#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);
}