algorithm/Math/ModularArithmetic/modulo.hpp

• View this file on GitHub
• Last update: 2025-08-31 07:47:07+00:00
• Include: #include "algorithm/Math/ModularArithmetic/modulo.hpp"

Required by

• 順列，組合せ，重複組合せ (algorithm/Math/Combinatorics/naive_combination.hpp)
• 動的Modint構造体 (algorithm/Math/ModularArithmetic/dynamic_modint.hpp)
• モジュラ逆数（乗法逆元） (algorithm/Math/ModularArithmetic/mod_inv.hpp)
• 繰り返し二乗法（mod付き） (algorithm/Math/ModularArithmetic/mod_pow.hpp)
• Modint構造体 (algorithm/Math/ModularArithmetic/modint.hpp)

Verified with

• verify/aoj-NTL_1_B-mod_pow.test.cpp
• verify/yosupo-convolution_mod-number_theoretic_transform.test.cpp
• verify/yosupo-point_set_range_composite-segment_tree.test.cpp
• verify/yosupo-range_affine_range_sum-lazy_segment_tree.test.cpp

Code

#ifndef ALGORITHM_MODULO_HPP
#define ALGORITHM_MODULO_HPP 1

#include <concepts>
#include <cstdint>

namespace algorithm {

namespace internal {

// return x mod m.
template <std::unsigned_integral Type>
constexpr std::uint32_t modulo(Type x, std::uint32_t mod) { return x % mod; }

// return x mod m.
template <std::unsigned_integral Type>
constexpr std::uint32_t modulo(Type x, std::int32_t mod) { return modulo(x, static_cast<std::uint32_t>(mod)); }

// return x mod m.
template <std::signed_integral Type>
constexpr std::uint32_t modulo(Type x, std::uint32_t mod) {
    x %= static_cast<std::int64_t>(mod);
    if(x < 0) x += static_cast<std::int64_t>(mod);
    return x;
}

// return x mod m.
template <std::signed_integral Type>
constexpr std::uint32_t modulo(Type x, std::int32_t mod) {
    x %= mod;
    if(x < 0) x += mod;
    return x;
}

}  // namespace internal

}  // namespace algorithm

#endif

#line 1 "algorithm/Math/ModularArithmetic/modulo.hpp"



#include <concepts>
#include <cstdint>

namespace algorithm {

namespace internal {

// return x mod m.
template <std::unsigned_integral Type>
constexpr std::uint32_t modulo(Type x, std::uint32_t mod) { return x % mod; }

// return x mod m.
template <std::unsigned_integral Type>
constexpr std::uint32_t modulo(Type x, std::int32_t mod) { return modulo(x, static_cast<std::uint32_t>(mod)); }

// return x mod m.
template <std::signed_integral Type>
constexpr std::uint32_t modulo(Type x, std::uint32_t mod) {
    x %= static_cast<std::int64_t>(mod);
    if(x < 0) x += static_cast<std::int64_t>(mod);
    return x;
}

// return x mod m.
template <std::signed_integral Type>
constexpr std::uint32_t modulo(Type x, std::int32_t mod) {
    x %= mod;
    if(x < 0) x += mod;
    return x;
}

}  // namespace internal

}  // namespace algorithm

Back to top page