C++ Library for Competitive Programming
View the Project on GitHub emthrm/cp-library
/* * @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; }