math_mod/pow_mod.hpp

• View this file on GitHub
• Last update: 2025-04-06 00:09:45+09:00
• Include: #include "math_mod/pow_mod.hpp"

Required by

• convolution/convolution.hpp
• convolution/convolution_arb.hpp
• convolution/convolution_int.hpp
• convolution/multi_convolution_truncated.hpp
• fps/fps_arb.hpp
• fps/fps_multivariate.hpp
• fps/fps_ntt_friendly.hpp
• math/group/rolling_hash.hpp
• math/group/rolling_hash.hpp
• math/is_prime.hpp
• math/multiplicative_function/euler_phi.hpp
• math/multiplicative_function/mobius.hpp
• math/multiplicative_function/sigma.hpp
• math/prime_factorize.hpp
• math_mod/butterfly.hpp
• math_mod/comb_large.hpp
• math_mod/primitive_root.hpp
• math_mod/primitive_root_64bit.hpp
• math_mod/primitive_root_64bit.hpp
• random/hash.hpp
• random/hash.hpp
• 文字の一点更新が可能文字列に対する動的なローリングハッシュ (string/dynamic_rolling_hash.hpp)
• 文字の一点更新が可能文字列に対する動的なローリングハッシュ (string/dynamic_rolling_hash.hpp)
• 文字の変更が行われない文字列に対する静的なローリングハッシュ (string/static_rolling_hash.hpp)
• 文字の変更が行われない文字列に対する静的なローリングハッシュ (string/static_rolling_hash.hpp)

Verified with

• verify/aoj/aoj_alds1_14_b.test.cpp
• verify/aoj/aoj_alds1_14_b.test.cpp
• verify/aoj/aoj_ntl_1_d.test.cpp
• verify/unit_test/famous_function_table.test.cpp
• verify/unit_test/isprime_table_extend.test.cpp
• verify/unit_test/large_fact_arb_mod.test.cpp
• verify/unit_test/lpf_table_extend.test.cpp
• verify/unit_test/monoid.test.cpp
• verify/unit_test/monoid.test.cpp
• verify/unit_test/prime_factorize_table.test.cpp
• verify/yosupo_convolution/convolution_arbitrary.test.cpp
• verify/yosupo_convolution/convolution_multi_truncated.test.cpp
• verify/yosupo_convolution/convolution_ntt_friendly.test.cpp
• verify/yosupo_fps/fps_composition.test.cpp
• verify/yosupo_fps/fps_composition_inv.test.cpp
• verify/yosupo_fps/fps_exp.test.cpp
• verify/yosupo_fps/fps_exp_arb.test.cpp
• verify/yosupo_fps/fps_inv.test.cpp
• verify/yosupo_fps/fps_inv_arb.test.cpp
• verify/yosupo_fps/fps_log.test.cpp
• verify/yosupo_fps/fps_log_arb.test.cpp
• verify/yosupo_fps/fps_multipoint_evaluation.test.cpp
• verify/yosupo_fps/fps_multipoint_evaluation_geometric.test.cpp
• verify/yosupo_fps/fps_pow.test.cpp
• verify/yosupo_fps/fps_product_of_polynomial_sequence.test.cpp
• verify/yosupo_fps/fps_sparse_exp.test.cpp
• verify/yosupo_fps/fps_sparse_inv.test.cpp
• verify/yosupo_fps/fps_sparse_log.test.cpp
• verify/yosupo_fps/fps_sparse_pow.test.cpp
• verify/yosupo_fps/fps_sprase_sqrt.test.cpp
• verify/yosupo_fps/fps_sqrt.test.cpp
• verify/yosupo_fps/poly_division.test.cpp
• verify/yosupo_fps/poly_interpolation.test.cpp
• verify/yosupo_fps/poly_interpolation_geometric.test.cpp
• verify/yosupo_fps/poly_inv.test.cpp
• verify/yosupo_fps/poly_root_finding.test.cpp
• verify/yosupo_fps/poly_sample_point_shift.test.cpp
• verify/yosupo_fps/poly_taylor_shift.test.cpp
• verify/yosupo_fps/poly_to_newton_basis.test.cpp
• verify/yosupo_math/enumerate_bell_number.test.cpp
• verify/yosupo_math/enumerate_stirling_number_of_the_first_kind.test.cpp
• verify/yosupo_math/factrize.test.cpp
• verify/yosupo_math/kth_term_of_linearly_recurrent_sequence.test.cpp
• verify/yosupo_math/many_factrials.test.cpp
• verify/yosupo_math/primality_test.test.cpp
• verify/yosupo_math/primitive_root.test.cpp
• verify/yosupo_math/primitive_root.test.cpp
• verify/yosupo_string/string_z_roliha.test.cpp
• verify/yosupo_string/string_z_roliha.test.cpp
• verify/yuki/yuki_1510.test.cpp

Code

#ifndef KK2_MATH_MOD_POW_MOD_HPP
#define KK2_MATH_MOD_POW_MOD_HPP 1

#include <cassert>

namespace kk2 {

template <class S, class T, class U> constexpr S pow_mod(T x, U n, T m) {
    assert(n >= 0);
    if (m == 1) return S(0);
    S _m = m, r = 1;
    S y = x % _m;
    if (y < 0) y += _m;
    while (n) {
        if (n & 1) r = (r * y) % _m;
        if (n >>= 1) y = (y * y) % _m;
    }
    return r;
}

} // namespace kk2

#endif // KK2_MATH_MOD_POW_MOD_HPP

#line 1 "math_mod/pow_mod.hpp"



#include <cassert>

namespace kk2 {

template <class S, class T, class U> constexpr S pow_mod(T x, U n, T m) {
    assert(n >= 0);
    if (m == 1) return S(0);
    S _m = m, r = 1;
    S y = x % _m;
    if (y < 0) y += _m;
    while (n) {
        if (n & 1) r = (r * y) % _m;
        if (n >>= 1) y = (y * y) % _m;
    }
    return r;
}

} // namespace kk2

Back to top page