test/yosupo-enumerate-quotients.test.cpp

View this file on GitHub
Last update: 2023-05-03 12:22:21+09:00
Problem: https://judge.yosupo.jp/problem/enumerate_quotients

Depends on

floor(sqrt(n)) (cpp/sqrt.hpp)

Code

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

#include "../cpp/sqrt.hpp"
#include <vector>
#include <algorithm>
#include <iostream>

int main() {
    long long n;
    std::cin >> n;
    std::vector<long long> v1, v2;
    long long m = sqrtll(n);
    for(long long i = 1; i <= m; i ++) {
        v1.push_back(n / i);
        v2.push_back(i);
    }
    if(v1.back() == v2.back()) v1.pop_back();

    std::cout << v1.size() + v2.size() << std::endl;
    reverse(v1.begin(), v1.end());
    for(long long e : v2) std::cout << e << " ";
    for(long long e : v1) std::cout << e << " ";
    std::cout << std::endl;

    return 0;
}

#line 1 "test/yosupo-enumerate-quotients.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_quotients"

#line 2 "cpp/sqrt.hpp"

/**
 * @brief floor(sqrt(n))
 * @param n 平方根を求めたい整数 long long 型で 0 <= n < 2^63 を満たす
 * @return long long
 */
long long sqrtll(long long n) { 
    // 3037000500 = ceil(sqrt(2^63))
    long long le = 0, ri = 3037000500; 
    while(ri - le > 1) {
        long long mid = (le + ri) / 2;
        if(mid * mid <= n) le = mid;
        else ri = mid;
    }
    return le;
}
#line 4 "test/yosupo-enumerate-quotients.test.cpp"
#include <vector>
#include <algorithm>
#include <iostream>

int main() {
    long long n;
    std::cin >> n;
    std::vector<long long> v1, v2;
    long long m = sqrtll(n);
    for(long long i = 1; i <= m; i ++) {
        v1.push_back(n / i);
        v2.push_back(i);
    }
    if(v1.back() == v2.back()) v1.pop_back();

    std::cout << v1.size() + v2.size() << std::endl;
    reverse(v1.begin(), v1.end());
    for(long long e : v2) std::cout << e << " ";
    for(long long e : v1) std::cout << e << " ";
    std::cout << std::endl;

    return 0;
}