test/library_checker/number_theory/enumerate_quotients.test.cpp

• View this file on GitHub
• Last update: 2024-11-04 03:12:13+09:00
• Problem: https://judge.yosupo.jp/problem/enumerate_quotients

Depends on

• Enumerate Quotients (商列挙) (lib/math/enumerate_quotients.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_quotients"
#include <bits/stdc++.h>
using namespace std;

#include "../../../lib/math/enumerate_quotients.hpp"

int main(){
    long long n; cin >> n;
    vector<tuple<long long, long long, long long>> a = enumerate_quotients(n);
    reverse(a.begin(), a.end());
    cout << (int) a.size() << "\n";
    for(auto [l, r, q] : a){
        cout << q << " ";
    }
    cout << "\n";
}

#line 1 "test/library_checker/number_theory/enumerate_quotients.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_quotients"
#include <bits/stdc++.h>
using namespace std;

#line 2 "lib/math/enumerate_quotients.hpp"

/**
 * @brief Enumerate Quotients (商列挙)
 * @docs docs/math/enumerate_quotients.md
 */

template <typename T>
vector<tuple<T, T, T>> enumerate_quotients(const T &n){
    vector<tuple<T, T, T>> res;
    for(T l = 1; l <= n;){
        const T quotient = n / l;
        const T r = n / quotient + 1;

        // [l, r)
        res.emplace_back(l, r, quotient);
        l = r;
    }
    return res;
}
#line 6 "test/library_checker/number_theory/enumerate_quotients.test.cpp"

int main(){
    long long n; cin >> n;
    vector<tuple<long long, long long, long long>> a = enumerate_quotients(n);
    reverse(a.begin(), a.end());
    cout << (int) a.size() << "\n";
    for(auto [l, r, q] : a){
        cout << q << " ";
    }
    cout << "\n";
}

Back to top page