tests/math/quotient/libchecker.test.cpp

• View this file on GitHub
• Last update: 2025-03-03 00:33:48+09:00
• Problem: https://judge.yosupo.jp/problem/enumerate_quotients

Depends on

• 商列挙 (library/math/quotient.hpp)

Code

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
using ll = long long;
using ull = unsigned long long;

#include "../../../cpp/library/math/quotient.hpp"
#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_quotients"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  ll n;
  cin >> n;
  vector<tuple<ll, ll, ll>> res = asalib::math::floor_quotient(n);

  vector<ll> ans(res.size());
  rep(i, res.size()) ans[i] = get<0>(res[i]);
  reverse(ans.begin(), ans.end());

  cout << ans.size() << '\n';
  for (ll x : ans) cout << x << ' ';
  cout << endl;
  return 0;
}

#line 1 "tests/math/quotient/libchecker.test.cpp"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
using ll = long long;
using ull = unsigned long long;

#line 2 "library/math/quotient.hpp"

#include <concepts>
#line 6 "library/math/quotient.hpp"
using namespace std;

namespace asalib {
  namespace math {
    template<integral T>
    constexpr vector<tuple<T, T, T>> floor_quotient(T n) {
      vector<tuple<T, T, T>> res;
      for (T i = 1; i <= n; ++i) {
        T v = n / i;
        res.push_back({ v, i, n / v });
        i = n / v;
      }
      return res;
    }

    template<integral T>
    constexpr vector<tuple<T, T, T>> ceil_quotient(T n) {
      vector<tuple<T, T, T>> res;
      for (T i = 1; i <= n; ++i) {
        T v = (n + i - 1) / i;
        if (i == n) {
          assert(v == 1);
          res.push_back({ v, i, i });
        }
        else {
          assert(v > 1);
          T j = (n + v - 2) / (v - 1) - 1;
          res.push_back({ v, i, j });
          i = j;
        }
      }
      return res;
    }
  }  // namespace math
}  // namespace asalib
#line 8 "tests/math/quotient/libchecker.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_quotients"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  ll n;
  cin >> n;
  vector<tuple<ll, ll, ll>> res = asalib::math::floor_quotient(n);

  vector<ll> ans(res.size());
  rep(i, res.size()) ans[i] = get<0>(res[i]);
  reverse(ans.begin(), ans.end());

  cout << ans.size() << '\n';
  for (ll x : ans) cout << x << ' ';
  cout << endl;
  return 0;
}

Back to top page