tetration_mod.hpp

SECTIONMath INCLUDEnoya/tetration_mod.hpp

计算固定底数的幂塔模任意正整数，并正确处理不互质和 \(0^0\)。

\[ \displaystyle a\uparrow\uparrow h \bmod m \]

Complexity: Time: O(sqrt(modulus) log modulus). Space: O(log modulus).

AC 记录：tetration_mod。

跳到代码 · GitHub ↗

Implementation

ReferenceSourceExpanded

当前头文件，省略 include guard；依赖见 #include。

/// @complexity Time: O(sqrt(modulus) log modulus).  Space: O(log modulus).

#include <cassert>
#include <cstdint>

namespace noya {

namespace tetration_mod_detail {

inline std::uint64_t totient(std::uint64_t val) {
  std::uint64_t res = val;
  for (std::uint64_t fct = 2; fct * fct <= val; fct++) {
    if (val % fct == 0) {
      res = res / fct * (fct - 1);
      do {
        val /= fct;
      } while (val % fct == 0);
    }
  }
  if (val != 1) {
    res = res / val * (val - 1);
  }
  return res;
}

inline std::uint64_t power(std::uint64_t bas, std::uint64_t exp,
                           std::uint64_t mod, bool &lar) {
  if (bas == 1 || exp == 0) {
    return 1;
  }
  std::uint64_t res = 1;
  lar = lar || bas >= mod;
  bas %= mod;
  while (true) {
    if (exp & 1) {
      unsigned __int128 prd = static_cast<unsigned __int128>(res) * bas;
      if (prd >= mod) {
        lar = true;
      }
      res = std::uint64_t(prd % mod);
    }
    exp >>= 1;
    if (exp == 0) {
      break;
    }
    unsigned __int128 squ = static_cast<unsigned __int128>(bas) * bas;
    if (squ >= mod) {
      lar = true;
    }
    bas = std::uint64_t(squ % mod);
  }
  return res;
}

inline std::uint64_t tower(std::uint64_t bas, std::uint64_t hei,
                           std::uint64_t mod, bool &lar) {
  if (bas == 0) {
    return (~hei) & 1ULL;
  }
  if (mod == 1) {
    lar = true;
    return 1;
  }
  if (bas == 1 || hei == 0) {
    return 1;
  }
  if (hei == 1) {
    lar = lar || bas >= mod;
    return bas % mod + std::uint64_t(lar) * mod;
  }
  std::uint64_t exp = tower(bas, hei - 1, totient(mod), lar);
  std::uint64_t res = power(bas, exp, mod, lar);
  return res + std::uint64_t(lar) * mod;
}

} // namespace tetration_mod_detail

/// @brief Compute a power tower of `hei` copies of `bas` modulo
/// `mod`, with `0^0 = 1`.  Recursing through Euler-totient moduli keeps
/// the exponent small; an extra "large" bit distinguishes a reduced exponent
/// from a genuinely small one when the base is not coprime to the modulus.
inline std::uint64_t tetration_mod(std::uint64_t bas, std::uint64_t hei,
                                   std::uint64_t mod) {
  assert(mod >= 1);
  bool lar = false;
  return tetration_mod_detail::tower(bas, hei, mod, lar) % mod;
}

} // namespace noya

#ifndef NOYA_TETRATION_MOD_HPP
#define NOYA_TETRATION_MOD_HPP 1

/// @complexity Time: O(sqrt(modulus) log modulus).  Space: O(log modulus).

#include <cassert>
#include <cstdint>

namespace noya {

namespace tetration_mod_detail {

inline std::uint64_t totient(std::uint64_t val) {
  std::uint64_t res = val;
  for (std::uint64_t fct = 2; fct * fct <= val; fct++) {
    if (val % fct == 0) {
      res = res / fct * (fct - 1);
      do {
        val /= fct;
      } while (val % fct == 0);
    }
  }
  if (val != 1) {
    res = res / val * (val - 1);
  }
  return res;
}

inline std::uint64_t power(std::uint64_t bas, std::uint64_t exp,
                           std::uint64_t mod, bool &lar) {
  if (bas == 1 || exp == 0) {
    return 1;
  }
  std::uint64_t res = 1;
  lar = lar || bas >= mod;
  bas %= mod;
  while (true) {
    if (exp & 1) {
      unsigned __int128 prd = static_cast<unsigned __int128>(res) * bas;
      if (prd >= mod) {
        lar = true;
      }
      res = std::uint64_t(prd % mod);
    }
    exp >>= 1;
    if (exp == 0) {
      break;
    }
    unsigned __int128 squ = static_cast<unsigned __int128>(bas) * bas;
    if (squ >= mod) {
      lar = true;
    }
    bas = std::uint64_t(squ % mod);
  }
  return res;
}

inline std::uint64_t tower(std::uint64_t bas, std::uint64_t hei,
                           std::uint64_t mod, bool &lar) {
  if (bas == 0) {
    return (~hei) & 1ULL;
  }
  if (mod == 1) {
    lar = true;
    return 1;
  }
  if (bas == 1 || hei == 0) {
    return 1;
  }
  if (hei == 1) {
    lar = lar || bas >= mod;
    return bas % mod + std::uint64_t(lar) * mod;
  }
  std::uint64_t exp = tower(bas, hei - 1, totient(mod), lar);
  std::uint64_t res = power(bas, exp, mod, lar);
  return res + std::uint64_t(lar) * mod;
}

} // namespace tetration_mod_detail

/// @brief Compute a power tower of `hei` copies of `bas` modulo
/// `mod`, with `0^0 = 1`.  Recursing through Euler-totient moduli keeps
/// the exponent small; an extra "large" bit distinguishes a reduced exponent
/// from a genuinely small one when the base is not coprime to the modulus.
inline std::uint64_t tetration_mod(std::uint64_t bas, std::uint64_t hei,
                                   std::uint64_t mod) {
  assert(mod >= 1);
  bool lar = false;
  return tetration_mod_detail::tower(bas, hei, mod, lar) % mod;
}

} // namespace noya

#endif // NOYA_TETRATION_MOD_HPP

#include <cassert>
#include <cstdint>

/// @complexity Time: O(sqrt(modulus) log modulus).  Space: O(log modulus).

namespace noya {

namespace tetration_mod_detail {

inline std::uint64_t totient(std::uint64_t val) {
  std::uint64_t res = val;
  for (std::uint64_t fct = 2; fct * fct <= val; fct++) {
    if (val % fct == 0) {
      res = res / fct * (fct - 1);
      do {
        val /= fct;
      } while (val % fct == 0);
    }
  }
  if (val != 1) {
    res = res / val * (val - 1);
  }
  return res;
}

inline std::uint64_t power(std::uint64_t bas, std::uint64_t exp,
                           std::uint64_t mod, bool &lar) {
  if (bas == 1 || exp == 0) {
    return 1;
  }
  std::uint64_t res = 1;
  lar = lar || bas >= mod;
  bas %= mod;
  while (true) {
    if (exp & 1) {
      unsigned __int128 prd = static_cast<unsigned __int128>(res) * bas;
      if (prd >= mod) {
        lar = true;
      }
      res = std::uint64_t(prd % mod);
    }
    exp >>= 1;
    if (exp == 0) {
      break;
    }
    unsigned __int128 squ = static_cast<unsigned __int128>(bas) * bas;
    if (squ >= mod) {
      lar = true;
    }
    bas = std::uint64_t(squ % mod);
  }
  return res;
}

inline std::uint64_t tower(std::uint64_t bas, std::uint64_t hei,
                           std::uint64_t mod, bool &lar) {
  if (bas == 0) {
    return (~hei) & 1ULL;
  }
  if (mod == 1) {
    lar = true;
    return 1;
  }
  if (bas == 1 || hei == 0) {
    return 1;
  }
  if (hei == 1) {
    lar = lar || bas >= mod;
    return bas % mod + std::uint64_t(lar) * mod;
  }
  std::uint64_t exp = tower(bas, hei - 1, totient(mod), lar);
  std::uint64_t res = power(bas, exp, mod, lar);
  return res + std::uint64_t(lar) * mod;
}

} // namespace tetration_mod_detail

/// @brief Compute a power tower of `hei` copies of `bas` modulo
/// `mod`, with `0^0 = 1`.  Recursing through Euler-totient moduli keeps
/// the exponent small; an extra "large" bit distinguishes a reduced exponent
/// from a genuinely small one when the base is not coprime to the modulus.
inline std::uint64_t tetration_mod(std::uint64_t bas, std::uint64_t hei,
                                   std::uint64_t mod) {
  assert(mod >= 1);
  bool lar = false;
  return tetration_mod_detail::tower(bas, hei, mod, lar) % mod;
}

} // namespace noya