整数商の列挙・添字

components/floor_quotients.hpp · GitHub で見る

共通ページ

#include "lib/components/floor_quotients.hpp"

FloorQuotients table(10);
auto values = table.values(); // {10,5,3,2,1}
auto i = table.index(5);      // 1
auto j = table.divided_index(0, 3); // values[j] == 10/3 == 3

FloorQuotients は、正の整数 \(i\) に対する \(\displaystyle \left\lfloor\frac{N}{i}\right\rfloor\) の異なる正の値を、降順で保持します。N = 0 では空です。整数平方根を積で補正し、添字の判定は整数演算で行います。

操作	内容・返り値
FloorQuotients(n = 0)	上限 n の表を作る
max_n() / root()	上限／その整数平方根
size() / values()	要素数／降順の const vector<uint64_t>&
large_size()	整数平方根より大きい要素の個数
contains(x)	x が表に含まれるか。0 は含まない
index(x)	表に含まれる正の x の添字
divided_index(i,d)	values()[i] / d の添字
swap(other)	二つの表を交換する

n は std::uint64_t です。index(x) の引数は表に含まれる値に限ります。任意の入力を調べる場合は先に contains(x) を呼んでください。divided_index(i,d) は i < size()、1 <= d <= values()[i] が必要です。この商も必ず表に含まれます。

コピーは独立し、ムーブ後の元の表は上限 0 の空表になります。巨大な n では表自身が大きくなるため、確保できるメモリの範囲で使ってください。

FloorQuotientRange(n = 0) は同じ商を昇順に列挙する、配列を保持しない範囲です。

#include "lib/components/floor_quotients.hpp"
#include <iostream>

FloorQuotientRange range(10);
for (auto x : range) std::cout << x << ' '; // 1 2 3 5 10

操作	内容・返り値
FloorQuotientRange(n = 0)	uint64_t の上限 n に対する範囲を作る
max_n() / root() / large_size()	上限／整数平方根／整数平方根より大きい商の個数
size() / empty()	要素数を uint64_t、空かどうかを bool で返す
range[i]	0 <= i < size() に対する昇順の第 i 要素を uint64_t で返す
begin() / end()	前方走査用のイテレータ。間接参照の返り値は uint64_t の値

n = 0 では空です。uint64_t 全域に対応し、int64_t を超える商もそのまま符号なし整数で返します。イテレータの走査中は元の範囲を保持してください。

FloorQuotients の構築・コピーは \(\displaystyle O(\sqrt n)\) 時間・空間、参照・添字取得・交換・ムーブ構築は \(O(1)\) 時間です。ムーブ代入では代入先の旧領域を解放します。

FloorQuotientRange の構築・コピー・各参照・イテレータの取得・増分は \(O(1)\) 時間・空間、全要素の列挙は \(\displaystyle O(\sqrt n)\) 時間です。

検証コード

• test/enumerate_quotients.test.cpp
• test/multiplicative_prefix_sum.test.cpp
• test/multiplicative_prefix_sum.test.cpp
• test/multiplicative_prefix_sum_large.test.cpp
• test/multiplicative_prefix_sum_large.test.cpp

コード

#ifndef FLOOR_QUOTIENTS_HPP
#define FLOOR_QUOTIENTS_HPP

#include <cassert>
#include <cmath>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <iterator>
#include <utility>
#include <vector>

namespace floor_quotient_detail {
inline std::uint64_t square_root(std::uint64_t n) {
	std::uint64_t root = std::sqrt(static_cast<long double>(n));
	while (__uint128_t(root) * root > n) --root;
	while (__uint128_t(root + 1) * (root + 1) <= n) ++root;
	return root;
}
inline std::uint64_t divide(std::uint64_t n, std::uint64_t divisor) {
	if constexpr (std::numeric_limits<double>::is_iec559 && std::numeric_limits<double>::radix == 2 && std::numeric_limits<double>::digits >= 53) {
		if (n <= (std::uint64_t(1) << 53)) {
			std::uint64_t value = double(n) / double(divisor);
			return value - (value * divisor > n);
		}
	}
	return n / divisor;
}
}

class FloorQuotientRange {
	std::uint64_t n_, root_, large_;

  public:
	explicit FloorQuotientRange(std::uint64_t n = 0) : n_(n), root_(floor_quotient_detail::square_root(n)), large_(root_ - (n < root_ * (root_ + 1))) {}
	std::uint64_t max_n() const { return n_; }
	std::uint64_t root() const { return root_; }
	std::uint64_t large_size() const { return large_; }
	std::uint64_t size() const { return root_ + large_; }
	bool empty() const { return !n_; }
	std::uint64_t operator[](std::uint64_t i) const {
		assert(i < size());
		return i < root_ ? i + 1 : floor_quotient_detail::divide(n_, size() - i);
	}
	class iterator {
		const FloorQuotientRange *range_ = nullptr;
		std::uint64_t index_ = 0;
		friend class FloorQuotientRange;
		iterator(const FloorQuotientRange *range, std::uint64_t i) : range_(range), index_(i) {}

	  public:
		using value_type = std::uint64_t;
		using difference_type = std::int64_t;
		using iterator_category = std::input_iterator_tag;
		using iterator_concept = std::forward_iterator_tag;
		using reference = value_type;
		using pointer = void;
		iterator() = default;
		value_type operator*() const { return (*range_)[index_]; }
		iterator &operator++() { ++index_; return *this; }
		iterator operator++(int) { auto result = *this; ++*this; return result; }
		bool operator==(const iterator &) const = default;
	};
	iterator begin() const { return iterator(this, 0); }
	iterator end() const { return iterator(this, size()); }
};

class FloorQuotients {
	std::uint64_t n_, root_ = 0;
	std::size_t large_ = 0;
	std::vector<std::uint64_t> values_;

  public:
	explicit FloorQuotients(std::uint64_t n = 0) : n_(n) {
		if (!n) return;
		root_ = floor_quotient_detail::square_root(n);
		large_ = n / (root_ + 1);
		values_.reserve(large_ + root_);
		for (std::size_t i = 1; i <= large_; ++i) values_.push_back(floor_quotient_detail::divide(n, i));
		for (auto x = root_; x; --x) values_.push_back(x);
	}
	FloorQuotients(const FloorQuotients&) = default;
	FloorQuotients& operator=(const FloorQuotients&) = default;
	FloorQuotients(FloorQuotients&& other) noexcept : FloorQuotients() { swap(other); }
	FloorQuotients& operator=(FloorQuotients&& other) noexcept {
		if (this != &other) { FloorQuotients empty; swap(empty); swap(other); }
		return *this;
	}
	void swap(FloorQuotients& other) noexcept {
		std::swap(n_, other.n_), std::swap(root_, other.root_), std::swap(large_, other.large_);
		values_.swap(other.values_);
	}
	std::uint64_t max_n() const { return n_; }
	std::uint64_t root() const { return root_; }
	std::size_t size() const { return values_.size(); }
	std::size_t large_size() const { return large_; }
	const std::vector<std::uint64_t>& values() const { return values_; }
	bool contains(std::uint64_t x) const { return x && x <= n_ && (x <= root_ || n_ / (n_ / x) == x); }
	std::size_t index(std::uint64_t x) const {
		assert(x && x <= n_);
		return x <= root_ ? size() - x : n_ / x - 1;
	}
	std::size_t divided_index(std::size_t i, std::uint64_t divisor) const {
		assert(i < size() && divisor && divisor <= values_[i]);
		if (i >= large_) return size() - values_[i] / divisor;
		const auto d = (i + 1) * divisor;
		return d <= large_ ? d - 1 : size() - n_ / d;
	}
};

#endif

Back to top page