1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123 | #pragma once
#include <ranges><--- Include file: not found. Please note: Cppcheck does not need standard library headers to get proper results.
#include <vector><--- Include file: not found. Please note: Cppcheck does not need standard library headers to get proper results.
#include <algorithm><--- Include file: not found. Please note: Cppcheck does not need standard library headers to get proper results.
#include <type_traits><--- Include file: not found. Please note: Cppcheck does not need standard library headers to get proper results.
#include "snippet/aliases.hpp"
#include "internal/dev_env.hpp"
#include "numeric/internal/divisors.hpp"
#include "numeric/modular/modint_interface.hpp"
#include "random/engine.hpp"
namespace uni {
namespace internal {
// Thanks to: https://37zigen.com/primitive-root/
template<modint_family Small, modint_family Large, modint_family Mint, std::unsigned_integral T>
T primitive_root(const T p) noexcept(NO_EXCEPT) {
std::vector<T> pows;
factorize<Small, Large>(p - 1, &pows);
{
std::ranges::sort(pows);
const auto rest = std::ranges::unique(pows);
pows.erase(ALL(rest));
}
ITRR(pow, pows) pow = (p - 1) / pow;<--- Shadow variable<--- Consider using std::transform algorithm instead of a raw loop.
if constexpr(dynamic_modint_family<Mint>) Mint::set_mod(p);
assert(Mint::mod() == p);
static random_engine_64bit rand;
while(true) {
const Mint x = rand();
if(x == Mint::zero) continue;
bool ok = true;
ITR(pow, pows) {<--- Shadow variable
if(x.pow(pow) == Mint::one) {<--- Consider using std::any_of algorithm instead of a raw loop.
ok = false;
break;
}
}
if(ok) return x.val();
}
return 0;
}
// Thanks to: atcoder::internal::primitive_root_constexpr
template<static_modint_family Mint>
constexpr u32 primitive_root_constexpr(u32 m) {
assert(Mint::mod() == m);
u32 divs[20]{}; divs[0] = 2;
u32 cnt = 1;
u64 x = (m - 1) / 2;
while(x % 2 == 0) x /= 2;
for(u64 i = 3; 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(u32 g = 2; ; g++) {
bool ok = true;
REP(i, cnt) {
if(Mint{ g }.pow((m - 1) / divs[i]) == 1) {
ok = false;
break;
}
}
if(ok) return g;
}
}
template<modint_family Small, modint_family Large = Small, std::integral Res = u64, bool FORCE_RANDOM = false>
constexpr Res primitive_root(const u64 p) noexcept(NO_EXCEPT) {
if constexpr(!FORCE_RANDOM) {
if(p == 2) return 1;
if(p == 167772161) return 3;
if(p == 469762049) return 3;
if(p == 754974721) return 11;
if(p == 998244353) return 3;
if(p == (UINT64_C(1) << 61) - 1) return 37;
}
if(std::is_constant_evaluated()) {
if constexpr(static_modint_family<Small> && std::same_as<Small, Large> && Small::mod() < (1U << 31)) {
assert(p <= std::numeric_limits<u32>::max());
return primitive_root_constexpr<Small>(p);
}
assert(false);
}
else {
if(p <= Small::max()) return primitive_root<Small, Large, Small, typename Small::value_type>(p);
else return primitive_root<Small, Large, Large, typename Large::value_type>(p);
}
}
} // namespace internal
} // namespace uni
|