約数列挙
(include/emthrm/math/divisor.hpp)

• View this file on GitHub
• Last update: 2023-02-23 21:59:12+09:00
• Include: #include "emthrm/math/divisor.hpp"

時間計算量

$O(\sqrt{N})$

仕様

名前	戻り値
template <typename T> std::vector<T> divisor(const T n);	$n$ の約数

参考文献

• 秋葉拓哉，岩田陽一，北川宜稔：プログラミングコンテストチャレンジブック [第2版]，p.111，マイナビ出版（2012）

Submissons

https://onlinejudge.u-aizu.ac.jp/solutions/problem/2932/review/4088339/emthrm/C++14

Verified with

• 数学/約数列挙 (test/math/divisor.test.cpp)

Code

#ifndef EMTHRM_MATH_DIVISOR_HPP_
#define EMTHRM_MATH_DIVISOR_HPP_

#include <algorithm>
#include <vector>

namespace emthrm {

template <typename T>
std::vector<T> divisor(const T n) {
  std::vector<T> res;
  T i = 1;
  for (; i * i < n; ++i) {
    if (n % i == 0) [[unlikely]] {
      res.emplace_back(i);
      res.emplace_back(n / i);
    }
  }
  if (i * i == n && n % i == 0) res.emplace_back(i);
  std::sort(res.begin(), res.end());
  return res;
}

}  // namespace emthrm

#endif  // EMTHRM_MATH_DIVISOR_HPP_

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



#include <algorithm>
#include <vector>

namespace emthrm {

template <typename T>
std::vector<T> divisor(const T n) {
  std::vector<T> res;
  T i = 1;
  for (; i * i < n; ++i) {
    if (n % i == 0) [[unlikely]] {
      res.emplace_back(i);
      res.emplace_back(n / i);
    }
  }
  if (i * i == n && n % i == 0) res.emplace_back(i);
  std::sort(res.begin(), res.end());
  return res;
}

}  // namespace emthrm

Back to top page