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

• View this file on GitHub
• Last update: 2025-08-17 00:21:01+09:00
• Include: #include "library/math/quotient.hpp"

概要

vector<tuple<T, T, T>> floor_quotient<T>(T N): $\displaystyle S = \left\lbrace \left\lfloor \dfrac{N}{x} \right\rfloor \mid x \in \mathbb{Z}, 1 \le x \le N \right\rbrace$ と、各要素についての $x$ の範囲を返す。

vector<tuple<T, T, T>> ceil_quotient<T>(T N): $\displaystyle S = \left\lbrace \left\lceil \dfrac{N}{x} \right\rceil \mid x \in \mathbb{Z}, 1 \le x \le N \right\rbrace$ と、各要素についての $x$ の範囲を返す。

計算量は $O(\sqrt{N})$ 。 いずれも $x$ について昇順ソートされている。 逆を言えば、商について降順ソートされている。

tuple<T, T, T> の値について

1. 商
2. 商がその値となる $x$ の最小値
3. 商がその値となる $x$ の最大値

つまり、値をそれぞれ $a, b, c$ としたときに、 $b \le x \le c$ となる $x$ すべてについて $\displaystyle \left\lfloor \dfrac{N}{x} \right\rfloor = a$ (or ceil) である。

検証コード

int main() {
  for (int i = 1; i <= 10000; ++i) {
    auto fl = asalib::math::floor_quotient(i);
    auto ce = asalib::math::ceil_quotient(i);
    // Debug(i, fl, ce);
    for (auto [v, l, r] : fl) {
      for (int x = l; x <= r; ++x) {
        assert(i / x == v);
      }
    }
    for (auto [v, l, r] : ce) {
      for (int x = l; x <= r; ++x) {
        assert((i + x - 1) / x == v);
      }
    }
  }
  return 0;
}

Verified with

• tests/math/quotient/abc132-f.test.cpp
• tests/math/quotient/arc150-b.test.cpp
• tests/math/quotient/libchecker.test.cpp

Code

#pragma once

#include <cassert>
#include <concepts>
#include <tuple>
#include <vector>
using namespace std;

namespace asalib::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.emplace_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.emplace_back(v, i, i);
      }
      else {
        assert(v > 1);
        T j = (n + v - 2) / (v - 1) - 1;
        res.emplace_back(v, i, j);
        i = j;
      }
    }
    return res;
  }
}  // namespace asalib::math

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

#include <cassert>
#include <concepts>
#include <tuple>
#include <vector>
using namespace std;

namespace asalib::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.emplace_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.emplace_back(v, i, i);
      }
      else {
        assert(v > 1);
        T j = (n + v - 2) / (v - 1) - 1;
        res.emplace_back(v, i, j);
        i = j;
      }
    }
    return res;
  }
}  // namespace asalib::math

Back to top page