test/math/Quotient.test.cpp

• View this file on GitHub
• Last update: 2023-06-26 21:08:22+09:00
• Problem: https://judge.yosupo.jp/problem/enumerate_quotients

Depends on

• Quotient - 商の集合 (lib/30-math/Quotient.cpp)

Code

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

#include <vector>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cassert>
using namespace std;
#include "../../lib/30-math/Quotient.cpp"

int main(void){
    cin.tie(0);ios::sync_with_stdio(false);
    long long N; cin >> N;
    auto vp = Quotient(N);
    int M = vp.size();
    cout << M << "\n";
    for(int i = 0; i<M; ++i) cout << vp[i].first << " \n"[i==M-1];
	return 0;
}

#line 1 "test/math/Quotient.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_quotients"

#include <vector>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cassert>
using namespace std;
#line 1 "lib/30-math/Quotient.cpp"
/*
 * @title Quotient - 商の集合
 * @docs md/math/Quotient.md
 */
inline static vector<pair<long long,long long>> Quotient(long long n) {
    assert(n > 0);
    long long b = sqrtl(n);
    long long l = b;
    while(n / l != b) ++l;
    vector<pair<long long,long long>> res = {{0,0}};
    for(long long i = 1; i <= l; ++i) {
        long long k = n / i;
        if(res.back().first == k) res.back().second++;
        else res.emplace_back(k,1);
    }
    for(long long i = b, r; 1 <= i; --i, l = r+1) {
        r = n / i;
        long long k = n / l;
        if(res.back().first == k) res.back().second = (r-l+1);
        else res.emplace_back(k,r-l+1);
    }
    reverse(res.begin(),res.end());
    res.pop_back();
    return res;
}
#line 10 "test/math/Quotient.test.cpp"

int main(void){
    cin.tie(0);ios::sync_with_stdio(false);
    long long N; cin >> N;
    auto vp = Quotient(N);
    int M = vp.size();
    cout << M << "\n";
    for(int i = 0; i<M; ++i) cout << vp[i].first << " \n"[i==M-1];
	return 0;
}

Back to top page