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 %lld\n", ans.x, ans.y);
	pp("%.20lf\n", (db) ans.x / ans.y);
}

LL的Stern-Brocot Tree模板

原文：https://www.cnblogs.com/coldchair/p/13110440.html