test/yosupo/enumerate_quotients.test.cpp

• View this file on GitHub
• Last update: 2024-01-08 17:31:43+09:00
• Problem: https://judge.yosupo.jp/problem/enumerate_quotients

Depends on

• Intervals with Equal Quotients (math/number-theory/quotients.hpp)

Code

#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");
    }
}

Back to top page