[go: up one dir, main page]

cplib-cpp

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub hitonanode/cplib-cpp

:heavy_check_mark: utilities/test/quotients.test.cpp

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_quotients"
#include "../quotients.hpp"

#include <iostream>
using namespace std;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    long long N;
    cin >> N;

    auto ret = get_quotients(N);
    cout << ret.size() << '\n';
    for (auto x : ret) cout << x << ' ';
    cout << '\n';
}
#line 1 "utilities/test/quotients.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_quotients"
#line 2 "utilities/quotients.hpp"
#include <algorithm>
#include <vector>

// Generate all quotients of n
// return: n/1, n/2, ..., n
// Complexity: O(sqrt(n))
template <class T = long long> std::vector<T> get_quotients(T n) {
    std::vector<T> res;
    for (T x = 1;; ++x) {
        if (x * x >= n) {
            const int sz = res.size();
            if (x * x == n) res.push_back(x);
            res.reserve(res.size() + sz);
            for (int i = sz - 1; i >= 0; --i) {
                T tmp = n / res.at(i);
                if (tmp < x) continue;
                if (tmp == x and tmp * tmp == n) continue;
                res.push_back(tmp);
            }
            return res;
        } else {
            res.push_back(x);
        }
    }
}
#line 3 "utilities/test/quotients.test.cpp"

#include <iostream>
using namespace std;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    long long N;
    cin >> N;

    auto ret = get_quotients(N);
    cout << ret.size() << '\n';
    for (auto x : ret) cout << x << ' ';
    cout << '\n';
}
Back to top page