Stern-Brocot Tree
(math/number-theory/stern_brocot_tree.hpp)

• View this file on GitHub
• Last update: 2024-01-08 17:31:43+09:00
• Include: #include "math/number-theory/stern_brocot_tree.hpp"

Description

Stern-Brocot tree は，有理数の探索に用いられる二分木である．

Operations

• pair<pair<long long, long long>, pair<long long, long long>> stern_brocot_tree_search(long long n, F cond)
  • 分母及び分子が $n$ 以下の既約分数 $p/q$ のうち，条件 $\mathrm{cond}(p/q)$ を満たす最大のもの $a/b$ と満たさない最小のもの $c/d$ を返す． $\mathrm{cond}(p/q)$ の単調性を仮定する．
  • 時間計算量: $O(f(n)\log n)$, $f(n)$ は $\mathrm{cond}(p/q)$ の計算量

Reference

• ABC294 F - Sugar Water 2 解説
• verify: https://yukicoder.me/submissions/857736

Verified with

• test/aoj/1208.test.cpp

Code

#pragma once
#include <utility>

/**
 * @brief Stern Brocot Tree
 */
template <typename F>
std::pair<std::pair<long long, long long>, std::pair<long long, long long>>
stern_brocot_tree_search(long long n, F cond) {
    long long a = 0, b = 1, c = 1, d = 0;
    while (true) {
        long long num = a + c, den = b + d;
        if (num > n || den > n) break;
        if (cond(num, den)) {
            long long k = 2;
            while ((num = a + c * k) <= n && (den = b + d * k) <= n &&
                   cond(num, den))
                k *= 2;
            k /= 2;
            a += c * k;
            b += d * k;
        } else {
            long long k = 2;
            while ((num = a * k + c) <= n && (den = b * k + d) <= n &&
                   !cond(num, den))
                k *= 2;
            k /= 2;
            c += a * k;
            d += b * k;
        }
    }
    return {{a, b}, {c, d}};
}

#line 2 "math/number-theory/stern_brocot_tree.hpp"
#include <utility>

/**
 * @brief Stern Brocot Tree
 */
template <typename F>
std::pair<std::pair<long long, long long>, std::pair<long long, long long>>
stern_brocot_tree_search(long long n, F cond) {
    long long a = 0, b = 1, c = 1, d = 0;
    while (true) {
        long long num = a + c, den = b + d;
        if (num > n || den > n) break;
        if (cond(num, den)) {
            long long k = 2;
            while ((num = a + c * k) <= n && (den = b + d * k) <= n &&
                   cond(num, den))
                k *= 2;
            k /= 2;
            a += c * k;
            b += d * k;
        } else {
            long long k = 2;
            while ((num = a * k + c) <= n && (den = b * k + d) <= n &&
                   !cond(num, den))
                k *= 2;
            k /= 2;
            c += a * k;
            d += b * k;
        }
    }
    return {{a, b}, {c, d}};
}

Back to top page