primitive_root
(src/math/primitive_root.hpp)

• View this file on GitHub
• Last update: 2024-11-09 02:03:28+09:00
• Include: #include "src/math/primitive_root.hpp"

primitive_root

int primitive_root(int m)

$m$ の原始根を返します．

制約

• $m$ は素数

計算量

• 期待 $O(\sqrt{m})$

Depends on

• pow_mod (src/math/pow_mod.hpp)
• template (src/template/template.hpp)

Required by

• convolution (src/convolution/convolution.hpp)
• convolution_arbitrary (src/convolution/convolution_arbitrary.hpp)
• convolution_ll (src/convolution/convolution_ll.hpp)
• FormalPowerSeries (src/fps/formal_power_series.hpp)
• FormalPowerSeriesArbitrary (src/fps/formal_power_series_arbitrary.hpp)
• FormalPowerSeriesLL (src/fps/formal_power_series_ll.hpp)
• wildcard_pattern_matching (src/string/wildcard_pattern_matching.hpp)

Verified with

• verify/library_checker/convolution/convolution.test.cpp
• verify/library_checker/convolution/convolution_mod_1000000007.test.cpp
• verify/library_checker/other/find_linear_recurrence.test.cpp
• verify/library_checker/other/kth_term_of_linearly_recurrent_sequence.test.cpp
• verify/library_checker/polynomial/division_of_polynomial.test.cpp
• verify/library_checker/polynomial/exp_of_formal_power_series.test.cpp
• verify/library_checker/polynomial/inv_of_formal_power_series.test.cpp
• verify/library_checker/polynomial/log_of_formal_power_series.test.cpp
• verify/library_checker/polynomial/polynomial_taylor_shift.test.cpp
• verify/library_checker/polynomial/pow_of_formal_power_series.test.cpp
• verify/library_checker/polynomial/product_of_polynomial_sequence.test.cpp
• verify/library_checker/string/wildcard_pattern_matching.test.cpp
• verify/library_checker/tree/frequency_table_of_tree_distance.test.cpp
• verify/unit_test/convolution/convolution_ll.test.cpp
• verify/yukicoder/1559.test.cpp

Code

#pragma once
#include "../template/template.hpp"
#include "./pow_mod.hpp"
constexpr int primitive_root(const 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;
    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(g, (m - 1) / divs[i], m) == 1) {
                ok = false;
                break;
            }
        }
        if(ok) return g;
    }
}

#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/math/pow_mod.hpp"
constexpr long long pow_mod(long long x, long long n, const long long mod) {
    assert(n >= 0 and mod >= 1);
    x %= mod;
    if(x < 0) x += mod;
    long long res = 1;
    while(n > 0) {
        if(n & 1) res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}
#line 4 "src/math/primitive_root.hpp"
constexpr int primitive_root(const 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;
    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(g, (m - 1) / divs[i], m) == 1) {
                ok = false;
                break;
            }
        }
        if(ok) return g;
    }
}

Back to top page