osa_k 法
(include/emthrm/math/osa_k.hpp)

• View this file on GitHub
• Last update: 2023-02-23 21:59:12+09:00
• Include: #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$ の素因数分解

参考文献

• http://www.osak.jp/diary/diary_201310.html#20131017

Submissons

https://atcoder.jp/contests/abc177/submissions/20504644

Depends on

• prime sieve (include/emthrm/math/prime_sieve.hpp)

Verified with

• 数学/osa_k 法 (test/math/osa_k.test.cpp)

Code

#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

Back to top page