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

• View this file on GitHub
• Last update: 2023-02-25 01:48:23+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2932

Depends on

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

Code

/*
 * @title 数学/約数列挙
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2932
 */

#include <iostream>
#include <vector>

#include "emthrm/math/divisor.hpp"

int main() {
  long long n;
  std::cin >> n;
  std::vector<long long> d = emthrm::divisor(n);
  d.pop_back();
  int ans1 = 0;
  const int ans2 = d.size();
  while (!d.empty()) {
    ++ans1;
    std::vector<long long> nxt;
    for (const long long e : d) {
      if (d.back() % e != 0) nxt.emplace_back(e);
    }
    d = nxt;
  }
  std::cout << ans1 << ' ' << ans2 << '\n';
  return 0;
}

#line 1 "test/math/divisor.test.cpp"
/*
 * @title 数学/約数列挙
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2932
 */

#include <iostream>
#include <vector>

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



#include <algorithm>
#line 6 "include/emthrm/math/divisor.hpp"

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


#line 11 "test/math/divisor.test.cpp"

int main() {
  long long n;
  std::cin >> n;
  std::vector<long long> d = emthrm::divisor(n);
  d.pop_back();
  int ans1 = 0;
  const int ans2 = d.size();
  while (!d.empty()) {
    ++ans1;
    std::vector<long long> nxt;
    for (const long long e : d) {
      if (d.back() % e != 0) nxt.emplace_back(e);
    }
    d = nxt;
  }
  std::cout << ans1 << ' ' << ans2 << '\n';
  return 0;
}

Back to top page