math/constexpr-primitive-root.hpp

• View this file on GitHub
• Last update: 2023-08-31 20:44:07+09:00
• Include: #include "math/constexpr-primitive-root.hpp"

Required by

• 周波数領域での値を保持するFPS (fps/dual-fps.hpp)
• Cooley-Tukey FFT Algorithm (ntt/cooley-tukey-ntt.hpp)
• ntt/multiplicative-convolution-mod-p.hpp
• 多変数巡回畳み込み (ntt/multivariate-circular-convolution.hpp)
• Rader's FFT Algorithm (ntt/rader-ntt.hpp)

Verified with

• verify/verify-unit-test/dual-fps.test.cpp
• verify/verify-unit-test/primitive-root.test.cpp
• verify/verify-yosupo-ntt/yosupo-convolution-arbitrarylengthntt.test.cpp
• verify/verify-yosupo-ntt/yosupo-convolution-on-z-pz.test.cpp
• verify/verify-yosupo-ntt/yosupo-multivariate-circular-convolution.test.cpp
• verify/verify-yuki/yuki-1504.test.cpp
• verify/verify-yuki/yuki-1783.test.cpp

Code

#pragma once

constexpr unsigned int constexpr_primitive_root(unsigned int mod) {
  using u32 = unsigned int;
  using u64 = unsigned long long;
  if(mod == 2) return 1;
  u64 m = mod - 1, ds[32] = {}, idx = 0;
  for (u64 i = 2; i * i <= m; ++i) {
    if (m % i == 0) {
      ds[idx++] = i;
      while (m % i == 0) m /= i;
    }
  }
  if (m != 1) ds[idx++] = m;
  for (u32 _pr = 2, flg = true;; _pr++, flg = true) {
    for (u32 i = 0; i < idx && flg; ++i) {
      u64 a = _pr, b = (mod - 1) / ds[i], r = 1;
      for (; b; a = a * a % mod, b >>= 1)
        if (b & 1) r = r * a % mod;
      if (r == 1) flg = false;
    }
    if (flg == true) return _pr;
  }
}

#line 2 "math/constexpr-primitive-root.hpp"

constexpr unsigned int constexpr_primitive_root(unsigned int mod) {
  using u32 = unsigned int;
  using u64 = unsigned long long;
  if(mod == 2) return 1;
  u64 m = mod - 1, ds[32] = {}, idx = 0;
  for (u64 i = 2; i * i <= m; ++i) {
    if (m % i == 0) {
      ds[idx++] = i;
      while (m % i == 0) m /= i;
    }
  }
  if (m != 1) ds[idx++] = m;
  for (u32 _pr = 2, flg = true;; _pr++, flg = true) {
    for (u32 i = 0; i < idx && flg; ++i) {
      u64 a = _pr, b = (mod - 1) / ds[i], r = 1;
      for (; b; a = a * a % mod, b >>= 1)
        if (b & 1) r = r * a % mod;
      if (r == 1) flg = false;
    }
    if (flg == true) return _pr;
  }
}

Back to top page