Compile time primitive root @param m must be prime @return primitive root (and minimum in now)
| 142 | // @param m must be prime |
| 143 | // @return primitive root (and minimum in now) |
| 144 | constexpr int primitive_root_constexpr(int m) { |
| 145 | if (m == 2) return 1; |
| 146 | if (m == 167772161) return 3; |
| 147 | if (m == 469762049) return 3; |
| 148 | if (m == 754974721) return 11; |
| 149 | if (m == 998244353) return 3; |
| 150 | int divs[20] = {}; |
| 151 | divs[0] = 2; |
| 152 | int cnt = 1; |
| 153 | int x = (m - 1) / 2; |
| 154 | while (x % 2 == 0) x /= 2; |
| 155 | for (int i = 3; (long long)(i)*i <= x; i += 2) { |
| 156 | if (x % i == 0) { |
| 157 | divs[cnt++] = i; |
| 158 | while (x % i == 0) { |
| 159 | x /= i; |
| 160 | } |
| 161 | } |
| 162 | } |
| 163 | if (x > 1) { |
| 164 | divs[cnt++] = x; |
| 165 | } |
| 166 | for (int g = 2;; g++) { |
| 167 | bool ok = true; |
| 168 | for (int i = 0; i < cnt; i++) { |
| 169 | if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) { |
| 170 | ok = false; |
| 171 | break; |
| 172 | } |
| 173 | } |
| 174 | if (ok) return g; |
| 175 | } |
| 176 | } |
| 177 | template <int m> constexpr int primitive_root = primitive_root_constexpr(m); |
| 178 | |
| 179 | // @param n `n < 2^32` |