This documentation is automatically generated by competitive-verifier/competitive-verifier
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/enumerate_quotients
#include "../Quotient-Range.cpp"
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
long long n;
cin >> n;
auto qr = quotient_range<long long>(n);
assert(qr[0].first.first == 1);
assert(qr.back().first.second == n);
for (int i = 0; i < qr.size() - 1; i++) {
assert(qr[i].first.second + 1 == qr[i + 1].first.first);
}
cout << qr.size() << endl;
reverse(qr.begin(), qr.end());
for (auto [rng, z] : qr) cout << z << " ";
cout << endl;
}
#line 1 "test/Quotient-Range.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/enumerate_quotients
#line 1 "Quotient-Range.cpp"
#include <bits/stdc++.h>
using namespace std;
template <class T>
vector<pair<pair<T, T>, T>> quotient_range(T n) {
//[l,r]:quotient=z
//[l,r]:increasing
// z:decreasing
// z=0 is not included
T m = 1;
vector<pair<pair<T, T>, T>> ret;
while (m * m <= n) {
ret.emplace_back(make_pair(m, m), n / m);
m++;
}
for (T i = m; i >= 1; i--) {
T L = n / (i + 1) + 1;
T R = n / i;
if (L <= R && ret.back().first.second < L) ret.emplace_back(make_pair(L, R), n / L);
}
return ret;
}
template <class T>
vector<pair<pair<T, T>, T>> quotient_range_ceil(T n) {
const T inf = numeric_limits<T>::max();
vector<pair<pair<T, T>, T>> res;
if (n == 1) {
res.push_back({{1, inf}, 1});
return res;
}
T m = 1;
while (m * m < n) {
res.push_back({{m, m + 1}, (n + m - 1) / m});
m++;
}
m = res.back().second - 1;
while (m >= 1) {
T l = (n + m - 1) / m;
T r = m > 1 ? (n + m - 2) / (m - 1) : inf;
if (l < r) res.push_back({{l, r}, m});
m--;
}
return res;
}
#line 3 "test/Quotient-Range.test.cpp"
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
long long n;
cin >> n;
auto qr = quotient_range<long long>(n);
assert(qr[0].first.first == 1);
assert(qr.back().first.second == n);
for (int i = 0; i < qr.size() - 1; i++) {
assert(qr[i].first.second + 1 == qr[i + 1].first.first);
}
cout << qr.size() << endl;
reverse(qr.begin(), qr.end());
for (auto [rng, z] : qr) cout << z << " ";
cout << endl;
}
Env | Name | Status | Elapsed | Memory |
---|---|---|---|---|
g++ | example_00 |
![]() |
5 ms | 4 MB |
g++ | max_00 |
![]() |
130 ms | 54 MB |
g++ | min_00 |
![]() |
5 ms | 4 MB |
g++ | min_01 |
![]() |
4 ms | 4 MB |
g++ | min_02 |
![]() |
4 ms | 4 MB |
g++ | min_03 |
![]() |
4 ms | 4 MB |
g++ | min_04 |
![]() |
4 ms | 4 MB |
g++ | min_05 |
![]() |
4 ms | 4 MB |
g++ | min_06 |
![]() |
4 ms | 4 MB |
g++ | min_07 |
![]() |
4 ms | 4 MB |
g++ | min_08 |
![]() |
4 ms | 4 MB |
g++ | polynom_p1p1m1_00 |
![]() |
147 ms | 53 MB |
g++ | polynom_p1p1m1_01 |
![]() |
72 ms | 29 MB |
g++ | polynom_p1p1z_00 |
![]() |
150 ms | 53 MB |
g++ | polynom_p1p1z_01 |
![]() |
71 ms | 29 MB |
g++ | polynom_p1zm1_00 |
![]() |
150 ms | 54 MB |
g++ | polynom_p1zm1_01 |
![]() |
73 ms | 29 MB |
g++ | random_00 |
![]() |
65 ms | 29 MB |
g++ | random_01 |
![]() |
102 ms | 54 MB |
g++ | random_small_00 |
![]() |
5 ms | 4 MB |
g++ | random_small_01 |
![]() |
4 ms | 4 MB |
g++ | random_small_02 |
![]() |
4 ms | 4 MB |
g++ | random_small_03 |
![]() |
4 ms | 4 MB |
g++ | random_small_04 |
![]() |
4 ms | 4 MB |
g++ | square_00 |
![]() |
54 ms | 29 MB |
g++ | square_01 |
![]() |
66 ms | 28 MB |
clang++ | example_00 |
![]() |
5 ms | 4 MB |
clang++ | max_00 |
![]() |
126 ms | 53 MB |
clang++ | min_00 |
![]() |
5 ms | 4 MB |
clang++ | min_01 |
![]() |
4 ms | 4 MB |
clang++ | min_02 |
![]() |
4 ms | 4 MB |
clang++ | min_03 |
![]() |
4 ms | 4 MB |
clang++ | min_04 |
![]() |
4 ms | 4 MB |
clang++ | min_05 |
![]() |
4 ms | 4 MB |
clang++ | min_06 |
![]() |
4 ms | 4 MB |
clang++ | min_07 |
![]() |
4 ms | 4 MB |
clang++ | min_08 |
![]() |
4 ms | 4 MB |
clang++ | polynom_p1p1m1_00 |
![]() |
146 ms | 53 MB |
clang++ | polynom_p1p1m1_01 |
![]() |
62 ms | 29 MB |
clang++ | polynom_p1p1z_00 |
![]() |
129 ms | 54 MB |
clang++ | polynom_p1p1z_01 |
![]() |
72 ms | 28 MB |
clang++ | polynom_p1zm1_00 |
![]() |
149 ms | 54 MB |
clang++ | polynom_p1zm1_01 |
![]() |
72 ms | 29 MB |
clang++ | random_00 |
![]() |
67 ms | 29 MB |
clang++ | random_01 |
![]() |
106 ms | 53 MB |
clang++ | random_small_00 |
![]() |
5 ms | 4 MB |
clang++ | random_small_01 |
![]() |
4 ms | 4 MB |
clang++ | random_small_02 |
![]() |
4 ms | 4 MB |
clang++ | random_small_03 |
![]() |
4 ms | 4 MB |
clang++ | random_small_04 |
![]() |
4 ms | 4 MB |
clang++ | square_00 |
![]() |
53 ms | 28 MB |
clang++ | square_01 |
![]() |
66 ms | 29 MB |