数学/$i^k \bmod m$ ($0 \leq i \leq n$)
(test/math/enumerate_k-th_power.test.cpp)

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

Depends on

• $i^k \bmod m$ ($0 \leq i \leq n$) (include/emthrm/math/enumerate_k-th_power.hpp)
• 繰り返し二乗法 / 二分累乗法 / バイナリ法 (include/emthrm/math/mod_pow.hpp)
• prime sieve (include/emthrm/math/prime_sieve.hpp)

Code

/*
 * @title 数学/$i^k \bmod m$ ($0 \leq i \leq n$)
 *
 * verification-helper: PROBLEM https://yukicoder.me/problems/no/1409
 */

#include <iostream>
#include <vector>

#include "emthrm/math/enumerate_k-th_power.hpp"

int main() {
  int t;
  std::cin >> t;
  while (t--) {
    int v, x;
    std::cin >> v >> x;
    const int p = x * v + 1;
    const std::vector<int> ps = emthrm::enumerate_kth_power(p - 1, x, p);
    std::vector<int> a;
    a.reserve(x);
    for (int i = 1; i < p; ++i) {
      if (ps[i] == 1) a.emplace_back(i);
    }
    for (int i = 0; i < x; ++i) {
      std::cout << a[i] << " \n"[i + 1 == x];
    }
  }
  return 0;
}

#line 1 "test/math/enumerate_k-th_power.test.cpp"
/*
 * @title 数学/$i^k \bmod m$ ($0 \leq i \leq n$)
 *
 * verification-helper: PROBLEM https://yukicoder.me/problems/no/1409
 */

#include <iostream>
#include <vector>

#line 1 "include/emthrm/math/enumerate_k-th_power.hpp"



#line 5 "include/emthrm/math/enumerate_k-th_power.hpp"

#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_sieve.hpp"



#include <numeric>
#line 6 "include/emthrm/math/prime_sieve.hpp"

namespace emthrm {

template <bool GETS_ONLY_PRIME>
std::vector<int> prime_sieve(const int n) {
  std::vector<int> smallest_prime_factor(n + 1), prime;
  std::iota(smallest_prime_factor.begin(), smallest_prime_factor.end(), 0);
  for (int i = 2; i <= n; ++i) {
    if (smallest_prime_factor[i] == i) [[unlikely]] prime.emplace_back(i);
    for (const int p : prime) {
      if (i * p > n || p > smallest_prime_factor[i]) break;
      smallest_prime_factor[i * p] = p;
    }
  }
  return GETS_ONLY_PRIME ? prime : smallest_prime_factor;
}

}  // namespace emthrm


#line 8 "include/emthrm/math/enumerate_k-th_power.hpp"

namespace emthrm {

std::vector<int> enumerate_kth_power(const int n, const int k, const int m) {
  const std::vector<int> smallest_prime_factor = prime_sieve<false>(n);
  std::vector<int> res(n + 1, 0);
  for (int i = 1; i <= n; ++i) {
    if (smallest_prime_factor[i] == i) [[unlikely]] {
      res[i] = mod_pow(i, k, m);
    } else {
      res[i] = static_cast<long long>(res[smallest_prime_factor[i]])
               * res[i / smallest_prime_factor[i]] % m;
    }
  }
  return res;
}

}  // namespace emthrm


#line 11 "test/math/enumerate_k-th_power.test.cpp"

int main() {
  int t;
  std::cin >> t;
  while (t--) {
    int v, x;
    std::cin >> v >> x;
    const int p = x * v + 1;
    const std::vector<int> ps = emthrm::enumerate_kth_power(p - 1, x, p);
    std::vector<int> a;
    a.reserve(x);
    for (int i = 1; i < p; ++i) {
      if (ps[i] == 1) a.emplace_back(i);
    }
    for (int i = 0; i < x; ++i) {
      std::cout << a[i] << " \n"[i + 1 == x];
    }
  }
  return 0;
}

Back to top page