LL的Stern-Brocot Tree模板

对于一个节点，应该记录两个二元组(A(x0,y0))和(B(x1,y1))，这个点的实际值是(C=frac{x0+x1}{y0+y1})。

当这个点的值(le 需要的值)，则下一步应该往右走，否则往左走。

每次走的时候二分一个最远的步数满足和原来的$le (状态相同，将其赋为新的)A(或)B$，这样再走一步就状态切换了。

若一开始(le)，则二分完后新的(A)还是(le 需要的值)，用它更新答案。

可以适当的封装函数（比如二分上界、判断大小）以简化代码。

Code：

#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, _b = y; i <= _b; i ++)
#define ff(i, x, y) for(int i = x, _b = y; i <  _b; i ++)
#define fd(i, x, y) for(int i = x, _b = y; i >= _b; i --)
#define ll long long
#define pp printf
#define hh pp("n")
using namespace std;

struct P {
    ll x, y;
    P(ll _x = 0, ll _y = 0) {
        x = _x, y = _y;
    }
};

const ll lim = 1e10;

#define db double
const db w = 5.2312312;

int chk(P a) {
    return a.x <= w * a.y;
}

ll get_mx(P a, P b) {
    ll s = lim;
    if(b.x) s = min(s, (lim - a.x) / b.x);
    if(b.y) s = min(s, (lim - a.y) / b.y);
    return s;
}

int main() {
    P a = P(0, 1), b = P(1, 0);
    P ans;
    while(1) {
        P c = P(a.x + b.x, a.y + b.y);
        if(c.x > lim || c.y > lim) break;
        if(chk(c)) {
            a = c;
            for(ll l = 1, r = get_mx(c, b); l <= r; ) {
                ll m = l + r >> 1;
                P d = P(c.x + b.x * m, c.y + b.y * m);
                if(chk(d)) a = d, l = m + 1; else r = m - 1;
            }
            ans = a;
        } else {
            b = c;
            for(ll l = 1, r = get_mx(c, a); l <= r; ) {
                ll m = l + r >> 1;
                P d = P(c.x + a.x * m, c.y + a.y * m);
                if(!chk(d)) b = d, l = m + 1; else r = m - 1;
            }
        }
    }
    pp("%lld %lldn", ans.x, ans.y);
    pp("%.20lfn", (db) ans.x / ans.y);
}