stern_brocot.hpp¶
在正有理数与 Stern–Brocot 树的左右路径间转换；用于分数区间、连分数式跳跃和有理逼近。
\[
\displaystyle \frac{a}{b}\oplus\frac{c}{d}=\frac{a+c}{b+d}
\]
Complexity: Time: O(log max(numerator,denominator)) run steps. Space: O(r), where r is the number of returned runs.
AC 记录：stern_brocot_tree。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(log max(numerator,denominator)) run steps.
/// Space: O(r), where r is the number of returned runs.
#include <cassert>
#include <cstdint>
#include <limits>
#include <numeric>
#include <optional>
#include <utility>
#include <vector>
namespace noya {
using stern_brocot_step = std::pair<char, std::uint64_t>;
/// @brief Run-length encoded L/R path from 1/1 to a positive reduced fraction.
inline std::vector<stern_brocot_step> stern_brocot_path(std::uint64_t num,
std::uint64_t den) {
assert(num >= 1 && den >= 1);
assert(std::gcd(num, den) == 1);
std::vector<stern_brocot_step> pat;
while (num != den) {
if (num < den) {
std::uint64_t cnt = (den - 1) / num;
pat.emplace_back('L', cnt);
den -= cnt * num;
} else {
std::uint64_t cnt = (num - 1) / den;
pat.emplace_back('R', cnt);
num -= cnt * den;
}
}
return pat;
}
/// @brief Decode a run-length encoded Stern-Brocot path to its reduced
/// fraction; asserts when a 64-bit numerator or denominator would overflow.
inline std::pair<std::uint64_t, std::uint64_t>
stern_brocot_fraction(const std::vector<stern_brocot_step> &pat) {
using u128 = unsigned __int128;
// The left and right neighbors are ln/ld and rn/rd.
u128 ln = 0;
u128 ld = 1;
u128 num = 1;
u128 den = 1;
u128 rn = 1;
u128 rd = 0;
constexpr u128 mx = std::numeric_limits<std::uint64_t>::max();
for (auto [dir, cnt] : pat) {
assert((dir == 'L' || dir == 'R') && cnt >= 1);
if (dir == 'L') {
rn = num + u128(cnt - 1) * ln;
rd = den + u128(cnt - 1) * ld;
num += u128(cnt) * ln;
den += u128(cnt) * ld;
} else {
ln = num + u128(cnt - 1) * rn;
ld = den + u128(cnt - 1) * rd;
num += u128(cnt) * rn;
den += u128(cnt) * rd;
}
assert(num <= mx && den <= mx);
}
return {std::uint64_t(num), std::uint64_t(den)};
}
/// @brief Return the Stern-Brocot node at the given depth on the root-to-node
/// path, or nullopt when the requested depth is greater than the node depth.
inline std::optional<std::pair<std::uint64_t, std::uint64_t>>
stern_brocot_ancestor(std::uint64_t dep, std::uint64_t num, std::uint64_t den) {
auto pat = stern_brocot_path(num, den);
std::vector<stern_brocot_step> pre;
for (auto [dir, cnt] : pat) {
std::uint64_t use = std::min(dep, cnt);
if (use > 0) {
pre.emplace_back(dir, use);
}
if (dep <= cnt) {
return stern_brocot_fraction(pre);
}
dep -= cnt;
}
if (dep == 0) {
return stern_brocot_fraction(pre);
}
return std::nullopt;
}
/// @brief Return the lowest common ancestor of positive reduced fractions a/b and c/d.
inline std::pair<std::uint64_t, std::uint64_t>
stern_brocot_lca(std::uint64_t a, std::uint64_t b, std::uint64_t c,
std::uint64_t d) {
auto lhs = stern_brocot_path(a, b);
auto rhs = stern_brocot_path(c, d);
std::vector<stern_brocot_step> pre;
for (std::size_t idx = 0; idx < std::min(lhs.size(), rhs.size()); idx++) {
if (lhs[idx].first != rhs[idx].first) {
break;
}
pre.emplace_back(lhs[idx].first,
std::min(lhs[idx].second, rhs[idx].second));
if (lhs[idx].second != rhs[idx].second) {
break;
}
}
return stern_brocot_fraction(pre);
}
/// @brief Return the open rational interval containing precisely the
/// descendants of a positive reduced fraction. The boundaries may be 0/1 or
/// 1/0.
inline std::pair<std::pair<std::uint64_t, std::uint64_t>,
std::pair<std::uint64_t, std::uint64_t>>
stern_brocot_subtree_range(std::uint64_t num, std::uint64_t den) {
using u128 = unsigned __int128;
auto pat = stern_brocot_path(num, den);
// The left and right boundaries are ln/ld and rn/rd.
u128 ln = 0;
u128 ld = 1;
u128 rn = 1;
u128 rd = 0;
for (auto [dir, cnt] : pat) {
if (dir == 'L') {
rn += u128(cnt) * ln;
rd += u128(cnt) * ld;
} else {
ln += u128(cnt) * rn;
ld += u128(cnt) * rd;
}
}
constexpr u128 mx = std::numeric_limits<std::uint64_t>::max();
assert(ln <= mx && ld <= mx);
assert(rn <= mx && rd <= mx);
return {{std::uint64_t(ln), std::uint64_t(ld)},
{std::uint64_t(rn), std::uint64_t(rd)}};
}
} // namespace noya
#ifndef NOYA_STERN_BROCOT_HPP
#define NOYA_STERN_BROCOT_HPP 1
/// @complexity Time: O(log max(numerator,denominator)) run steps.
/// Space: O(r), where r is the number of returned runs.
#include <cassert>
#include <cstdint>
#include <limits>
#include <numeric>
#include <optional>
#include <utility>
#include <vector>
namespace noya {
using stern_brocot_step = std::pair<char, std::uint64_t>;
/// @brief Run-length encoded L/R path from 1/1 to a positive reduced fraction.
inline std::vector<stern_brocot_step> stern_brocot_path(std::uint64_t num,
std::uint64_t den) {
assert(num >= 1 && den >= 1);
assert(std::gcd(num, den) == 1);
std::vector<stern_brocot_step> pat;
while (num != den) {
if (num < den) {
std::uint64_t cnt = (den - 1) / num;
pat.emplace_back('L', cnt);
den -= cnt * num;
} else {
std::uint64_t cnt = (num - 1) / den;
pat.emplace_back('R', cnt);
num -= cnt * den;
}
}
return pat;
}
/// @brief Decode a run-length encoded Stern-Brocot path to its reduced
/// fraction; asserts when a 64-bit numerator or denominator would overflow.
inline std::pair<std::uint64_t, std::uint64_t>
stern_brocot_fraction(const std::vector<stern_brocot_step> &pat) {
using u128 = unsigned __int128;
// The left and right neighbors are ln/ld and rn/rd.
u128 ln = 0;
u128 ld = 1;
u128 num = 1;
u128 den = 1;
u128 rn = 1;
u128 rd = 0;
constexpr u128 mx = std::numeric_limits<std::uint64_t>::max();
for (auto [dir, cnt] : pat) {
assert((dir == 'L' || dir == 'R') && cnt >= 1);
if (dir == 'L') {
rn = num + u128(cnt - 1) * ln;
rd = den + u128(cnt - 1) * ld;
num += u128(cnt) * ln;
den += u128(cnt) * ld;
} else {
ln = num + u128(cnt - 1) * rn;
ld = den + u128(cnt - 1) * rd;
num += u128(cnt) * rn;
den += u128(cnt) * rd;
}
assert(num <= mx && den <= mx);
}
return {std::uint64_t(num), std::uint64_t(den)};
}
/// @brief Return the Stern-Brocot node at the given depth on the root-to-node
/// path, or nullopt when the requested depth is greater than the node depth.
inline std::optional<std::pair<std::uint64_t, std::uint64_t>>
stern_brocot_ancestor(std::uint64_t dep, std::uint64_t num, std::uint64_t den) {
auto pat = stern_brocot_path(num, den);
std::vector<stern_brocot_step> pre;
for (auto [dir, cnt] : pat) {
std::uint64_t use = std::min(dep, cnt);
if (use > 0) {
pre.emplace_back(dir, use);
}
if (dep <= cnt) {
return stern_brocot_fraction(pre);
}
dep -= cnt;
}
if (dep == 0) {
return stern_brocot_fraction(pre);
}
return std::nullopt;
}
/// @brief Return the lowest common ancestor of positive reduced fractions a/b and c/d.
inline std::pair<std::uint64_t, std::uint64_t>
stern_brocot_lca(std::uint64_t a, std::uint64_t b, std::uint64_t c,
std::uint64_t d) {
auto lhs = stern_brocot_path(a, b);
auto rhs = stern_brocot_path(c, d);
std::vector<stern_brocot_step> pre;
for (std::size_t idx = 0; idx < std::min(lhs.size(), rhs.size()); idx++) {
if (lhs[idx].first != rhs[idx].first) {
break;
}
pre.emplace_back(lhs[idx].first,
std::min(lhs[idx].second, rhs[idx].second));
if (lhs[idx].second != rhs[idx].second) {
break;
}
}
return stern_brocot_fraction(pre);
}
/// @brief Return the open rational interval containing precisely the
/// descendants of a positive reduced fraction. The boundaries may be 0/1 or
/// 1/0.
inline std::pair<std::pair<std::uint64_t, std::uint64_t>,
std::pair<std::uint64_t, std::uint64_t>>
stern_brocot_subtree_range(std::uint64_t num, std::uint64_t den) {
using u128 = unsigned __int128;
auto pat = stern_brocot_path(num, den);
// The left and right boundaries are ln/ld and rn/rd.
u128 ln = 0;
u128 ld = 1;
u128 rn = 1;
u128 rd = 0;
for (auto [dir, cnt] : pat) {
if (dir == 'L') {
rn += u128(cnt) * ln;
rd += u128(cnt) * ld;
} else {
ln += u128(cnt) * rn;
ld += u128(cnt) * rd;
}
}
constexpr u128 mx = std::numeric_limits<std::uint64_t>::max();
assert(ln <= mx && ld <= mx);
assert(rn <= mx && rd <= mx);
return {{std::uint64_t(ln), std::uint64_t(ld)},
{std::uint64_t(rn), std::uint64_t(rd)}};
}
} // namespace noya
#endif // NOYA_STERN_BROCOT_HPP
#include <cassert>
#include <cstdint>
#include <limits>
#include <numeric>
#include <optional>
#include <utility>
#include <vector>
/// @complexity Time: O(log max(numerator,denominator)) run steps.
/// Space: O(r), where r is the number of returned runs.
namespace noya {
using stern_brocot_step = std::pair<char, std::uint64_t>;
/// @brief Run-length encoded L/R path from 1/1 to a positive reduced fraction.
inline std::vector<stern_brocot_step> stern_brocot_path(std::uint64_t num,
std::uint64_t den) {
assert(num >= 1 && den >= 1);
assert(std::gcd(num, den) == 1);
std::vector<stern_brocot_step> pat;
while (num != den) {
if (num < den) {
std::uint64_t cnt = (den - 1) / num;
pat.emplace_back('L', cnt);
den -= cnt * num;
} else {
std::uint64_t cnt = (num - 1) / den;
pat.emplace_back('R', cnt);
num -= cnt * den;
}
}
return pat;
}
/// @brief Decode a run-length encoded Stern-Brocot path to its reduced
/// fraction; asserts when a 64-bit numerator or denominator would overflow.
inline std::pair<std::uint64_t, std::uint64_t>
stern_brocot_fraction(const std::vector<stern_brocot_step> &pat) {
using u128 = unsigned __int128;
// The left and right neighbors are ln/ld and rn/rd.
u128 ln = 0;
u128 ld = 1;
u128 num = 1;
u128 den = 1;
u128 rn = 1;
u128 rd = 0;
constexpr u128 mx = std::numeric_limits<std::uint64_t>::max();
for (auto [dir, cnt] : pat) {
assert((dir == 'L' || dir == 'R') && cnt >= 1);
if (dir == 'L') {
rn = num + u128(cnt - 1) * ln;
rd = den + u128(cnt - 1) * ld;
num += u128(cnt) * ln;
den += u128(cnt) * ld;
} else {
ln = num + u128(cnt - 1) * rn;
ld = den + u128(cnt - 1) * rd;
num += u128(cnt) * rn;
den += u128(cnt) * rd;
}
assert(num <= mx && den <= mx);
}
return {std::uint64_t(num), std::uint64_t(den)};
}
/// @brief Return the Stern-Brocot node at the given depth on the root-to-node
/// path, or nullopt when the requested depth is greater than the node depth.
inline std::optional<std::pair<std::uint64_t, std::uint64_t>>
stern_brocot_ancestor(std::uint64_t dep, std::uint64_t num, std::uint64_t den) {
auto pat = stern_brocot_path(num, den);
std::vector<stern_brocot_step> pre;
for (auto [dir, cnt] : pat) {
std::uint64_t use = std::min(dep, cnt);
if (use > 0) {
pre.emplace_back(dir, use);
}
if (dep <= cnt) {
return stern_brocot_fraction(pre);
}
dep -= cnt;
}
if (dep == 0) {
return stern_brocot_fraction(pre);
}
return std::nullopt;
}
/// @brief Return the lowest common ancestor of positive reduced fractions a/b and c/d.
inline std::pair<std::uint64_t, std::uint64_t>
stern_brocot_lca(std::uint64_t a, std::uint64_t b, std::uint64_t c,
std::uint64_t d) {
auto lhs = stern_brocot_path(a, b);
auto rhs = stern_brocot_path(c, d);
std::vector<stern_brocot_step> pre;
for (std::size_t idx = 0; idx < std::min(lhs.size(), rhs.size()); idx++) {
if (lhs[idx].first != rhs[idx].first) {
break;
}
pre.emplace_back(lhs[idx].first,
std::min(lhs[idx].second, rhs[idx].second));
if (lhs[idx].second != rhs[idx].second) {
break;
}
}
return stern_brocot_fraction(pre);
}
/// @brief Return the open rational interval containing precisely the
/// descendants of a positive reduced fraction. The boundaries may be 0/1 or
/// 1/0.
inline std::pair<std::pair<std::uint64_t, std::uint64_t>,
std::pair<std::uint64_t, std::uint64_t>>
stern_brocot_subtree_range(std::uint64_t num, std::uint64_t den) {
using u128 = unsigned __int128;
auto pat = stern_brocot_path(num, den);
// The left and right boundaries are ln/ld and rn/rd.
u128 ln = 0;
u128 ld = 1;
u128 rn = 1;
u128 rd = 0;
for (auto [dir, cnt] : pat) {
if (dir == 'L') {
rn += u128(cnt) * ln;
rd += u128(cnt) * ld;
} else {
ln += u128(cnt) * rn;
ld += u128(cnt) * rd;
}
}
constexpr u128 mx = std::numeric_limits<std::uint64_t>::max();
assert(ln <= mx && ld <= mx);
assert(rn <= mx && rd <= mx);
return {{std::uint64_t(ln), std::uint64_t(ld)},
{std::uint64_t(rn), std::uint64_t(rd)}};
}
} // namespace noya