math_mod/primitive_root.hpp

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

Depends on

• 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_mod/butterfly.hpp
• math_mod/comb_large.hpp

Verified with

• verify/unit_test/large_fact_arb_mod.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/kth_term_of_linearly_recurrent_sequence.test.cpp
• verify/yosupo_math/many_factrials.test.cpp
• verify/yuki/yuki_1510.test.cpp

Code

#ifndef KK2_MATH_MOD_PRIMITIVE_ROOT_HPP
#define KK2_MATH_MOD_PRIMITIVE_ROOT_HPP 1

#include "pow_mod.hpp"

namespace kk2 {

constexpr int primitive_root_constexpr(int m) {
    if (m == 2) return 1;
    if (m == 167772161) return 3;
    if (m == 469762049) return 3;
    if (m == 754974721) return 11;
    if (m == 998244353) return 3;
    if (m == 1107296257) return 10;
    int divs[20] = {};
    divs[0] = 2;
    int cnt = 1;
    int x = (m - 1) / 2;
    while (x % 2 == 0) x /= 2;
    for (int i = 3; (long long)(i)*i <= x; i += 2) {
        if (x % i == 0) {
            divs[cnt++] = i;
            while (x % i == 0) { x /= i; }
        }
    }
    if (x > 1) { divs[cnt++] = x; }
    for (int g = 2;; g++) {
        bool ok = true;
        for (int i = 0; i < cnt; i++) {
            if (pow_mod<long long>(g, (m - 1) / divs[i], m) == 1) {
                ok = false;
                break;
            }
        }
        if (ok) return g;
    }
}

template <int m> static constexpr int primitive_root = primitive_root_constexpr(m);

} // namespace kk2

#endif // KK2_MATH_MOD_PRIMITIVE_ROOT_HPP

#line 1 "math_mod/primitive_root.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


#line 5 "math_mod/primitive_root.hpp"

namespace kk2 {

constexpr int primitive_root_constexpr(int m) {
    if (m == 2) return 1;
    if (m == 167772161) return 3;
    if (m == 469762049) return 3;
    if (m == 754974721) return 11;
    if (m == 998244353) return 3;
    if (m == 1107296257) return 10;
    int divs[20] = {};
    divs[0] = 2;
    int cnt = 1;
    int x = (m - 1) / 2;
    while (x % 2 == 0) x /= 2;
    for (int i = 3; (long long)(i)*i <= x; i += 2) {
        if (x % i == 0) {
            divs[cnt++] = i;
            while (x % i == 0) { x /= i; }
        }
    }
    if (x > 1) { divs[cnt++] = x; }
    for (int g = 2;; g++) {
        bool ok = true;
        for (int i = 0; i < cnt; i++) {
            if (pow_mod<long long>(g, (m - 1) / divs[i], m) == 1) {
                ok = false;
                break;
            }
        }
        if (ok) return g;
    }
}

template <int m> static constexpr int primitive_root = primitive_root_constexpr(m);

} // namespace kk2

Back to top page