数学/原始根判定
(test/math/is_primitive_root.test.cpp)

• View this file on GitHub
• Last update: 2023-02-25 16:35:06+09:00
• Problem: https://yukicoder.me/problems/no/1409

Depends on

• オイラーの $\varphi$ 関数 (Euler's totient function) (include/emthrm/math/euler_phi.hpp)
• 原始根 (primitive root) 判定 (include/emthrm/math/is_primitive_root.hpp)
• 繰り返し二乗法 / 二分累乗法 / バイナリ法 (include/emthrm/math/mod_pow.hpp)
• 素因数分解 (prime factorization) (include/emthrm/math/prime_factorization.hpp)

Code

/*
 * @title 数学/原始根判定
 *
 * verification-helper: PROBLEM https://yukicoder.me/problems/no/1409
 */

#include <algorithm>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>

#include "emthrm/math/is_primitive_root.hpp"
#include "emthrm/math/mod_pow.hpp"

int main() {
  int t;
  std::cin >> t;
  std::mt19937_64 engine(std::random_device {} ());
  while (t--) {
    int v, x;
    std::cin >> v >> x;
    const int p = v * x + 1;
    std::uniform_int_distribution<int> dist(1, p - 1);
    int root = 0;
    do {
      root = dist(engine);
    } while (!emthrm::is_primitive_root(root, p));
    std::vector<int> a(x, emthrm::mod_pow(root, v, p));
    a.front() = 1;
    std::partial_sum(a.begin(), a.end(), a.begin(),
                     [p](const int l, const int r) -> int {
                       return static_cast<long long>(l) * r % p;
                     });
    std::sort(a.begin(), a.end());
    for (int i = 0; i < x; ++i) {
      std::cout << a[i] << " \n"[i + 1 == x];
    }
  }
  return 0;
}

#line 1 "test/math/is_primitive_root.test.cpp"
/*
 * @title 数学/原始根判定
 *
 * verification-helper: PROBLEM https://yukicoder.me/problems/no/1409
 */

#include <algorithm>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>

#line 1 "include/emthrm/math/is_primitive_root.hpp"



#line 5 "include/emthrm/math/is_primitive_root.hpp"
#include <map>
#line 7 "include/emthrm/math/is_primitive_root.hpp"
#include <ranges>
#include <utility>
#line 10 "include/emthrm/math/is_primitive_root.hpp"

#line 1 "include/emthrm/math/euler_phi.hpp"



#include <cassert>

namespace emthrm {

long long euler_phi(long long n) {
  assert(n >= 1);
  long long res = n;
  for (long long i = 2; i * i <= n; ++i) {
    if (n % i == 0) [[unlikely]] {
      res -= res / i;
      while (n % i == 0) n /= i;
    }
  }
  return n > 1 ? res - res / n : res;
}

}  // namespace emthrm


#line 1 "include/emthrm/math/mod_pow.hpp"



namespace emthrm {

long long mod_pow(long long x, long long n, const int m) {
  if ((x %= m) < 0) x += m;
  long long res = 1;
  for (; n > 0; n >>= 1) {
    if (n & 1) res = (res * x) % m;
    x = (x * x) % m;
  }
  return res;
}

}  // namespace emthrm


#line 1 "include/emthrm/math/prime_factorization.hpp"



#line 6 "include/emthrm/math/prime_factorization.hpp"

namespace emthrm {

template <typename T>
std::vector<std::pair<T, int>> prime_factorization(T n) {
  std::vector<std::pair<T, int>> res;
  for (T i = 2; i * i <= n; ++i) {
    if (n % i == 0) [[unlikely]] {
      int exponent = 0;
      for (; n % i == 0; n /= i) {
        ++exponent;
      }
      res.emplace_back(i, exponent);
    }
  }
  if (n > 1) res.emplace_back(n, 1);
  return res;
}

}  // namespace emthrm


#line 14 "include/emthrm/math/is_primitive_root.hpp"

namespace emthrm {

bool is_primitive_root(long long root, const int m) {
  if ((root %= m) < 0) root += m;
  if (std::gcd(root, m) > 1) return false;
  static std::map<int, int> phi;
  if (!phi.contains(m)) phi[m] = euler_phi(m);
  const int phi_m = phi[m];
  static std::map<int, std::vector<int>> primes;
  if (!primes.contains(phi_m)) {
    // GCC 12 adopted P2415.
    const std::vector<std::pair<int, int>> pf = prime_factorization(phi_m);
    const auto ev = pf | std::views::keys;
    // const auto ev = prime_factorization(phi_m) | std::views::keys;
    primes[phi_m] = std::vector<int>(ev.begin(), ev.end());
  }
  return std::none_of(primes[phi_m].begin(), primes[phi_m].end(),
                      [root, phi_m, m](const int p) -> bool {
                        return mod_pow(root, phi_m / p, m) == 1;
                      });
}

}  // namespace emthrm


#line 15 "test/math/is_primitive_root.test.cpp"

int main() {
  int t;
  std::cin >> t;
  std::mt19937_64 engine(std::random_device {} ());
  while (t--) {
    int v, x;
    std::cin >> v >> x;
    const int p = v * x + 1;
    std::uniform_int_distribution<int> dist(1, p - 1);
    int root = 0;
    do {
      root = dist(engine);
    } while (!emthrm::is_primitive_root(root, p));
    std::vector<int> a(x, emthrm::mod_pow(root, v, p));
    a.front() = 1;
    std::partial_sum(a.begin(), a.end(), a.begin(),
                     [p](const int l, const int r) -> int {
                       return static_cast<long long>(l) * r % p;
                     });
    std::sort(a.begin(), a.end());
    for (int i = 0; i < x; ++i) {
      std::cout << a[i] << " \n"[i + 1 == x];
    }
  }
  return 0;
}

Back to top page