decimal_power_mod.hpp¶

SECTIONMath INCLUDEnoya/decimal_power_mod.hpp

指数以超长十进制字符串给出时计算模幂，不要求底数与模数互质。

\[ \displaystyle a^e\equiv r\;(\bmod m) \]

Complexity: Time: O(d log m) bit operations for d decimal exponent digits. Space: O(1) beyond the exponent string.

Implementation¶

ReferenceSourceExpanded

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

/// @complexity Time: O(d log m) bit operations for d decimal exponent digits.
/// Space: O(1) beyond the exponent string.

#include <cassert>
#include <cstdint>
#include <string_view>

namespace noya {

/// @brief Compute bas^exp modulo an arbitrary positive 64-bit modulus
/// from a decimal exponent of any length, without coprimality assumptions.
inline std::uint64_t decimal_power_mod(std::uint64_t bas, std::string_view exp,
                                       std::uint64_t mod) {
  assert(mod >= 1);
  assert(!exp.empty());
  using u128 = unsigned __int128;
  auto mul = [&](std::uint64_t a, std::uint64_t b) {
    return std::uint64_t(u128(a) * b % mod);
  };
  auto pw = [&](std::uint64_t val, int deg) {
    std::uint64_t res = 1 % mod;
    while (deg > 0) {
      if (deg & 1) {
        res = mul(res, val);
      }
      val = mul(val, val);
      deg >>= 1;
    }
    return res;
  };
  bas %= mod;
  std::uint64_t res = 1 % mod;
  for (char dig : exp) {
    assert('0' <= dig && dig <= '9');
    res = mul(pw(res, 10), pw(bas, dig - '0'));
  }
  return res;
}

} // namespace noya

#ifndef NOYA_DECIMAL_POWER_MOD_HPP
#define NOYA_DECIMAL_POWER_MOD_HPP 1

/// @complexity Time: O(d log m) bit operations for d decimal exponent digits.
/// Space: O(1) beyond the exponent string.

#include <cassert>
#include <cstdint>
#include <string_view>

namespace noya {

/// @brief Compute bas^exp modulo an arbitrary positive 64-bit modulus
/// from a decimal exponent of any length, without coprimality assumptions.
inline std::uint64_t decimal_power_mod(std::uint64_t bas, std::string_view exp,
                                       std::uint64_t mod) {
  assert(mod >= 1);
  assert(!exp.empty());
  using u128 = unsigned __int128;
  auto mul = [&](std::uint64_t a, std::uint64_t b) {
    return std::uint64_t(u128(a) * b % mod);
  };
  auto pw = [&](std::uint64_t val, int deg) {
    std::uint64_t res = 1 % mod;
    while (deg > 0) {
      if (deg & 1) {
        res = mul(res, val);
      }
      val = mul(val, val);
      deg >>= 1;
    }
    return res;
  };
  bas %= mod;
  std::uint64_t res = 1 % mod;
  for (char dig : exp) {
    assert('0' <= dig && dig <= '9');
    res = mul(pw(res, 10), pw(bas, dig - '0'));
  }
  return res;
}

} // namespace noya

#endif // NOYA_DECIMAL_POWER_MOD_HPP

#include <cassert>
#include <cstdint>
#include <string_view>

/// @complexity Time: O(d log m) bit operations for d decimal exponent digits.
/// Space: O(1) beyond the exponent string.

namespace noya {

/// @brief Compute bas^exp modulo an arbitrary positive 64-bit modulus
/// from a decimal exponent of any length, without coprimality assumptions.
inline std::uint64_t decimal_power_mod(std::uint64_t bas, std::string_view exp,
                                       std::uint64_t mod) {
  assert(mod >= 1);
  assert(!exp.empty());
  using u128 = unsigned __int128;
  auto mul = [&](std::uint64_t a, std::uint64_t b) {
    return std::uint64_t(u128(a) * b % mod);
  };
  auto pw = [&](std::uint64_t val, int deg) {
    std::uint64_t res = 1 % mod;
    while (deg > 0) {
      if (deg & 1) {
        res = mul(res, val);
      }
      val = mul(val, val);
      deg >>= 1;
    }
    return res;
  };
  bas %= mod;
  std::uint64_t res = 1 % mod;
  for (char dig : exp) {
    assert('0' <= dig && dig <= '9');
    res = mul(pw(res, 10), pw(bas, dig - '0'));
  }
  return res;
}

} // namespace noya