test/verify/yosupo-enumerate-quotients.test.cpp

• View this file on GitHub
• Last update: 2026-08-10 14:29:01+00:00
• Problem: https://judge.yosupo.jp/problem/enumerate_quotients

Depends on

• Enumerate Quotients (商列挙) (math/number-theory/enumerate-quotients.hpp)

Code

// clang-format off
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/enumerate_quotients
// clang-format on

#include <iostream>

#include "../../math/number-theory/enumerate-quotients.hpp"

using namespace std;

int main() {
  long long n;
  cin >> n;
  auto quotients = enumerate_quotients(n);
  cout << quotients.size() << endl;
  for (auto&& [q, l, r] : quotients) {
    cout << q << " ";
  }
  cout << endl;
}

#line 1 "test/verify/yosupo-enumerate-quotients.test.cpp"
// clang-format off
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/enumerate_quotients
// clang-format on

#include <iostream>

#line 2 "math/number-theory/enumerate-quotients.hpp"

#include <algorithm>
#include <tuple>
#include <vector>

template <typename T>
std::vector<std::tuple<T, T, T> > enumerate_quotients(T n) {
  T l = 1;
  std::vector<std::tuple<T, T, T> > quotients;
  while (l <= n) {
    T q = n / l;
    T r = n / q + 1;
    quotients.emplace_back(q, l, r);
    l = r;
  }
  std::reverse(quotients.begin(), quotients.end());
  return quotients;
}
#line 8 "test/verify/yosupo-enumerate-quotients.test.cpp"

using namespace std;

int main() {
  long long n;
  cin >> n;
  auto quotients = enumerate_quotients(n);
  cout << quotients.size() << endl;
  for (auto&& [q, l, r] : quotients) {
    cout << q << " ";
  }
  cout << endl;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	2 ms	4 MB
g++	max_00	AC	126 ms	54 MB
g++	min_00	AC	2 ms	4 MB
g++	min_01	AC	2 ms	4 MB
g++	min_02	AC	2 ms	4 MB
g++	min_03	AC	2 ms	4 MB
g++	min_04	AC	2 ms	4 MB
g++	min_05	AC	2 ms	4 MB
g++	min_06	AC	2 ms	4 MB
g++	min_07	AC	2 ms	4 MB
g++	min_08	AC	2 ms	4 MB
g++	polynom_p1p1m1_00	AC	138 ms	54 MB
g++	polynom_p1p1m1_01	AC	54 ms	29 MB
g++	polynom_p1p1z_00	AC	113 ms	53 MB
g++	polynom_p1p1z_01	AC	57 ms	29 MB
g++	polynom_p1zm1_00	AC	136 ms	54 MB
g++	polynom_p1zm1_01	AC	55 ms	29 MB
g++	random_00	AC	65 ms	29 MB
g++	random_01	AC	84 ms	53 MB
g++	random_small_00	AC	2 ms	4 MB
g++	random_small_01	AC	2 ms	4 MB
g++	random_small_02	AC	2 ms	4 MB
g++	random_small_03	AC	2 ms	4 MB
g++	random_small_04	AC	2 ms	4 MB
g++	square_00	AC	46 ms	29 MB
g++	square_01	AC	56 ms	29 MB
clang++	example_00	AC	2 ms	4 MB
clang++	max_00	AC	117 ms	54 MB
clang++	min_00	AC	2 ms	4 MB
clang++	min_01	AC	2 ms	4 MB
clang++	min_02	AC	2 ms	4 MB
clang++	min_03	AC	2 ms	4 MB
clang++	min_04	AC	2 ms	4 MB
clang++	min_05	AC	2 ms	4 MB
clang++	min_06	AC	2 ms	4 MB
clang++	min_07	AC	2 ms	4 MB
clang++	min_08	AC	2 ms	4 MB
clang++	polynom_p1p1m1_00	AC	138 ms	53 MB
clang++	polynom_p1p1m1_01	AC	56 ms	29 MB
clang++	polynom_p1p1z_00	AC	148 ms	53 MB
clang++	polynom_p1p1z_01	AC	57 ms	29 MB
clang++	polynom_p1zm1_00	AC	119 ms	54 MB
clang++	polynom_p1zm1_01	AC	70 ms	29 MB
clang++	random_00	AC	68 ms	29 MB
clang++	random_01	AC	85 ms	53 MB
clang++	random_small_00	AC	2 ms	4 MB
clang++	random_small_01	AC	2 ms	4 MB
clang++	random_small_02	AC	2 ms	4 MB
clang++	random_small_03	AC	2 ms	4 MB
clang++	random_small_04	AC	2 ms	4 MB
clang++	square_00	AC	49 ms	29 MB
clang++	square_01	AC	64 ms	29 MB

Back to top page