Stern–Brocot Tree の圧縮経路

components/stern_brocot_path.hpp · GitHub で見る

共通ページ

Stern–Brocot Tree の内部部品です。ユークリッド互除法で根からの連続移動を順に取り出します。

関数・型	内容・返り値	計算量
`stern_brocot_detail::Path<U>`	符号なし整数の分子・分母を持つ圧縮経路イテレータ	—（型）
`Path(numerator,denominator)`	正の分子・分母から構築。約分されていなくてもよい	\(O(1)\)
`empty()`	経路を最後まで取り出したか	\(O(1)\)
`right()`	次の区間が右への移動であるか。`!empty()` が必要	\(O(1)\)
`pop()`	次の区間の移動回数を返し、残りの経路へ進む。`!empty()` が必要。方向は呼ぶ前に `right()` で取得	\(O(1)\)

構築・各操作は \(O(1)\) 時間、経路全体は分子・分母の最大値を \(M\) として \(O(\log M)\) 時間、追加空間は \(O(1)\) です。

検証コード

コード

#ifndef STERN_BROCOT_PATH_HPP
#define STERN_BROCOT_PATH_HPP

#include <cassert>
#include <concepts>

namespace stern_brocot_detail {
template <std::unsigned_integral U>
class Path {
	U a, b;
public:
	Path(U numerator, U denominator) : a(numerator), b(denominator) { assert(a && b); }
	bool empty() const { return a == b; }
	bool right() const { return a > b; }
	U pop() {
		assert(!empty());
		if (right()) { U k = (a - 1) / b; a -= k * b; return k; }
		U k = (b - 1) / a; b -= k * a; return k;
	}
};
}

#endif

#line 1 "components/stern_brocot_path.hpp"



#include <cassert>
#include <concepts>

namespace stern_brocot_detail {
template <std::unsigned_integral U>
class Path {
	U a, b;
public:
	Path(U numerator, U denominator) : a(numerator), b(denominator) { assert(a && b); }
	bool empty() const { return a == b; }
	bool right() const { return a > b; }
	U pop() {
		assert(!empty());
		if (right()) { U k = (a - 1) / b; a -= k * b; return k; }
		U k = (b - 1) / a; b -= k * a; return k;
	}
};
}