sbt_fraction
クラス · Stern-Brocot 木
struct sbt_fraction;
概要
既約分数 (Stern-Brocot 木のノード)
正の有理数を p/q で表す。0 は 0/1、+∞ は 1/0 として扱える。 比較は __int128 でクロス積を取りオーバーフローを避ける。
計算量
- すべての操作が $O(1)$
構築・破棄
| 名前 | 説明 | 計算量 |
|---|---|---|
(constructor) |
(1) 0/1を構築する (2) 分子p、分母qの分数を構築する |
$O(1)$ |
演算子
| 名前 | 説明 | 計算量 |
|---|---|---|
operator== |
分子と分母が等しいか返す | $O(1)$ |
operator<=> |
クロス積で大小を比較する | $O(1)$ |
メンバ変数
| 名前 | 説明 | 計算量 |
|---|---|---|
q |
分子pと分母q | $O(1)$ |
メンバの詳細
(constructor)
// (1)
constexpr sbt_fraction();
// (2)
constexpr sbt_fraction(std::int64_t p, std::int64_t q);
(1) 0/1を構築する
- 計算量: $O(1)$
(2) 分子p、分母qの分数を構築する
- 計算量: $O(1)$
関連項目
stern_brocot_tree— Stern-Brocot 木