sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_quotients" #include <bits/stdc++.h> #include "../../math/number-theory/quotients.hpp" using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); long long N; cin >> N; auto qr = quotient_ranges(N); vector<long long> ans; for (auto [l, r] : qr) ans.push_back(N / l); reverse(ans.begin(), ans.end()); int k = ans.size(); cout << k << endl; for (int i = 0; i < k; ++i) { cout << ans[i] << (i < k - 1 ? " " : "\n"); } }
#line 1 "test/yosupo/enumerate_quotients.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/enumerate_quotients" #include <bits/stdc++.h> #line 3 "math/number-theory/quotients.hpp" /** * @brief Intervals with Equal Quotients */ template <typename T> std::vector<std::pair<T, T>> quotient_ranges(T n) { std::vector<std::pair<T, T>> ret; T i = 1; while (i <= n) { T q = n / i; T j = n / q + 1; ret.emplace_back(i, j); i = j; } return ret; } #line 6 "test/yosupo/enumerate_quotients.test.cpp" using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); long long N; cin >> N; auto qr = quotient_ranges(N); vector<long long> ans; for (auto [l, r] : qr) ans.push_back(N / l); reverse(ans.begin(), ans.end()); int k = ans.size(); cout << k << endl; for (int i = 0; i < k; ++i) { cout << ans[i] << (i < k - 1 ? " " : "\n"); } }