rational_approximation.hpp¶
在分子、分母均有上界时，求给定有理数两侧最接近的最简分数。
\[
\displaystyle \frac{L}{R}\le\frac{x}{y}\le\frac{U}{V}
\]
Complexity: Time: \(O(\log \max (x , y))\). Space: \(O(1)\).
Source: Library Checker
AC 记录：rational_approximation。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
// SPDX-License-Identifier: Apache-2.0
// Adapted from Library Checker, with changes for libra.
// Sources and license: third_party/README.md.
/// @complexity Time: O(log max(x,y)). Space: O(1).
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <utility>
namespace noya {
struct bounded_rational {
std::int64_t num = 0;
std::int64_t den = 1;
};
/// @brief Find the closest reduced fractions on both sides of x/y whose
/// numerators and denominators are at most lim. Maximal Stern--Brocot jumps
/// follow Euclidean remainders, capped by both coordinate bounds. Missing
/// lower and upper answers are represented by 0/1 and 1/0.
inline std::pair<bounded_rational, bounded_rational>
rational_approximation(std::int64_t lim, std::int64_t x, std::int64_t y) {
assert(lim >= 1 && x >= 1 && y >= 1);
bounded_rational lo{0, 1}, hi{1, 0};
auto advance = [&](bounded_rational &a, bounded_rational b, std::int64_t k) {
if (b.num) k = std::min(k, (lim - a.num) / b.num);
if (b.den) k = std::min(k, (lim - a.den) / b.den);
// The bounds are applied before multiplying, so both coordinates fit.
a.num += k * b.num;
a.den += k * b.den;
return k;
};
// x = lo.den * target.num - lo.num * target.den,
// y = hi.num * target.den - hi.den * target.num.
while (true) {
std::int64_t ls = advance(lo, hi, x / y);
x -= ls * y;
if (x == 0) {
hi = lo;
break;
}
std::int64_t rs = advance(hi, lo, y / x);
y -= rs * x;
if (y == 0) {
lo = hi;
break;
}
if (ls == 0 && rs == 0) break;
}
return {lo, hi};
}
} // namespace noya
// NOYA_RATIONAL_APPROXIMATION_HPP
#ifndef NOYA_RATIONAL_APPROXIMATION_HPP
#define NOYA_RATIONAL_APPROXIMATION_HPP 1
// SPDX-License-Identifier: Apache-2.0
// Adapted from Library Checker, with changes for libra.
// Sources and license: third_party/README.md.
/// @complexity Time: O(log max(x,y)). Space: O(1).
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <utility>
namespace noya {
struct bounded_rational {
std::int64_t num = 0;
std::int64_t den = 1;
};
/// @brief Find the closest reduced fractions on both sides of x/y whose
/// numerators and denominators are at most lim. Maximal Stern--Brocot jumps
/// follow Euclidean remainders, capped by both coordinate bounds. Missing
/// lower and upper answers are represented by 0/1 and 1/0.
inline std::pair<bounded_rational, bounded_rational>
rational_approximation(std::int64_t lim, std::int64_t x, std::int64_t y) {
assert(lim >= 1 && x >= 1 && y >= 1);
bounded_rational lo{0, 1}, hi{1, 0};
auto advance = [&](bounded_rational &a, bounded_rational b, std::int64_t k) {
if (b.num) k = std::min(k, (lim - a.num) / b.num);
if (b.den) k = std::min(k, (lim - a.den) / b.den);
// The bounds are applied before multiplying, so both coordinates fit.
a.num += k * b.num;
a.den += k * b.den;
return k;
};
// x = lo.den * target.num - lo.num * target.den,
// y = hi.num * target.den - hi.den * target.num.
while (true) {
std::int64_t ls = advance(lo, hi, x / y);
x -= ls * y;
if (x == 0) {
hi = lo;
break;
}
std::int64_t rs = advance(hi, lo, y / x);
y -= rs * x;
if (y == 0) {
lo = hi;
break;
}
if (ls == 0 && rs == 0) break;
}
return {lo, hi};
}
} // namespace noya
#endif // NOYA_RATIONAL_APPROXIMATION_HPP
// SPDX-License-Identifier: Apache-2.0
// Adapted from Library Checker, with changes for libra.
// Sources and license: third_party/README.md.
/// @complexity Time: O(log max(x,y)). Space: O(1).
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <utility>
namespace noya {
struct bounded_rational {
std::int64_t num = 0;
std::int64_t den = 1;
};
/// @brief Find the closest reduced fractions on both sides of x/y whose
/// numerators and denominators are at most lim. Maximal Stern--Brocot jumps
/// follow Euclidean remainders, capped by both coordinate bounds. Missing
/// lower and upper answers are represented by 0/1 and 1/0.
inline std::pair<bounded_rational, bounded_rational>
rational_approximation(std::int64_t lim, std::int64_t x, std::int64_t y) {
assert(lim >= 1 && x >= 1 && y >= 1);
bounded_rational lo{0, 1}, hi{1, 0};
auto advance = [&](bounded_rational &a, bounded_rational b, std::int64_t k) {
if (b.num) k = std::min(k, (lim - a.num) / b.num);
if (b.den) k = std::min(k, (lim - a.den) / b.den);
// The bounds are applied before multiplying, so both coordinates fit.
a.num += k * b.num;
a.den += k * b.den;
return k;
};
// x = lo.den * target.num - lo.num * target.den,
// y = hi.num * target.den - hi.den * target.num.
while (true) {
std::int64_t ls = advance(lo, hi, x / y);
x -= ls * y;
if (x == 0) {
hi = lo;
break;
}
std::int64_t rs = advance(hi, lo, y / x);
y -= rs * x;
if (y == 0) {
lo = hi;
break;
}
if (ls == 0 && rs == 0) break;
}
return {lo, hi};
}
} // namespace noya
// NOYA_RATIONAL_APPROXIMATION_HPP