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

• View this file on GitHub
• Last update: 2025-03-03 00:33:48+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 <concepts>
#include <tuple>
#include <vector>
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 2 "library/math/quotient.hpp"

#include <concepts>
#include <tuple>
#include <vector>
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

Back to top page