C++ Library for Competitive Programming
#include "emthrm/math/osa_k.hpp"
prime sieve を用いた素因数分解である。
$\langle O(N), O(\log{N}) \rangle$
struct OsaK;
名前 | 説明 |
---|---|
const std::vector<int> smallest_prime_factor |
$i$ の最小素因数 |
名前 | 効果・戻り値 |
---|---|
explicit OsaK(const int n); |
$n$ 以下に対するオブジェクトを構築する。 |
std::vector<std::pair<int, int>> query(int n) const; |
$n$ の素因数分解 |
https://atcoder.jp/contests/abc177/submissions/20504644
#ifndef EMTHRM_MATH_OSA_K_HPP_
#define EMTHRM_MATH_OSA_K_HPP_
#include <utility>
#include <vector>
#include "emthrm/math/prime_sieve.hpp"
namespace emthrm {
struct OsaK {
const std::vector<int> smallest_prime_factor;
explicit OsaK(const int n) : smallest_prime_factor(prime_sieve<false>(n)) {}
std::vector<std::pair<int, int>> query(int n) const {
std::vector<std::pair<int, int>> res;
while (n > 1) {
const int prime = smallest_prime_factor[n];
int exponent = 0;
for (; smallest_prime_factor[n] == prime; n /= prime) {
++exponent;
}
res.emplace_back(prime, exponent);
}
return res;
}
};
} // namespace emthrm
#endif // EMTHRM_MATH_OSA_K_HPP_
#line 1 "include/emthrm/math/osa_k.hpp"
#include <utility>
#include <vector>
#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/osa_k.hpp"
namespace emthrm {
struct OsaK {
const std::vector<int> smallest_prime_factor;
explicit OsaK(const int n) : smallest_prime_factor(prime_sieve<false>(n)) {}
std::vector<std::pair<int, int>> query(int n) const {
std::vector<std::pair<int, int>> res;
while (n > 1) {
const int prime = smallest_prime_factor[n];
int exponent = 0;
for (; smallest_prime_factor[n] == prime; n /= prime) {
++exponent;
}
res.emplace_back(prime, exponent);
}
return res;
}
};
} // namespace emthrm