Farey Sequence
记 \(n\) 阶 Farey Sequence 为 \(L_n\) ， \(L_n\) 即为集合 \(\{\frac{y}{x}\mid (x,y)=1\land1\leq x\leq n\}\) 中的数从小到大写下来，如 \(L_5=[\frac01,\frac15,\frac14,\frac13,\frac25,\frac12,\frac35,\frac23,\frac34,\frac45,\frac11]\) 。
一个比较显然的是 \(L_n\) 的长度为 \(\sum_{i=1}^{n}\varphi(i)+1\) 。
观察 \(L_n\) 中的相邻两项 \(\frac{a}{b},\frac{c}{d}\) 其中 \(\frac{a}{b}<\frac{c}{d}\) ，可以发现 \(\frac{a}{b}-\frac{c}{d}=\frac{1}{bd}\) ， 虽然不会证但是确实是对的。
实际上反过来也是对的，当 \(\frac{a}{b}-\frac{c}{d}=\frac{1}{bd}\) 时， \(\frac{a}{b},\frac{c}{d}\) 在 \(L_{\max\{b,d\}}\) 中相邻。
根据上述的性质还能推出另一个结论：假设 \(\frac{a}{b},\frac{p}{q},\frac{c}{d}\) 为相邻三项，那么有 \(\frac{p}{q}=\frac{a+c}{b+d}\) 。
那么可以通过上述性质构造 \(L_n\) 。具体来说已经构造了若干项，最近的两项为 \(\frac{a}{b},\frac{c}{d}\) ，假设接下的一项为 \(\frac{p}{q}\) 。通过上述的性质列方程，最后可以得到 \(p,q\) 关于一个参数 \(k\) 的表达式，即 \(p=kc-a,q=kd-b\) 。由于 \(\frac{p}{q}-\frac{c}{d}=\frac{cb-da}{d(kd-b)}\) ，所以 \(k\) 越大 \(\frac{p}{q}\) 和 \(\frac{c}{d}\) 越接近，那么 \(k\) 取最大值即 \(\lfloor \frac{n+b}{d}\rfloor\) 。所以最后就有如下递推式：
\[\begin{aligned} k & = \lfloor\frac{n+b}{d}\rfloor\\ p & =kc-a\\ q & =kd-b\\ \end{aligned} \]根据上述式子递推即可。
具体内容可以看： Farey Sequence 。
例题： FRACTION - Sort fractions 。
Stern-Brocot Tree
Stern-Brocot Tree 把所有的最简分数放到了一棵二叉搜索树上，建立方式是一种简单的构造，在二分精确值上有比较好的作用。
具体来说可以看下面这张图：
注意到构造方法就是每个节点的权等于左右两条虚线的值分子分母分别相加，如果要构建也是比较方便的。
在二分这方面，可以注意到如果转了一次向，比如先左后右，那么目前的权是 \(L+R\) ，左儿子是 \(2L+R\) ，左儿子的右儿子是 \(3L+2R\) ，由于权是分子分母分别相加，就是说分母分子都至少翻了一倍，所以如果限定了分母的最大值是 \(V\) ，那么最多转 \(O(\log V)\) 次向。根据这个性质，只需要在一条直链上二分，复杂度就是 \(O(\log^2V)\) 的。
标签：frac,Sequence,Tree,Farey,Brocot,Stern From： https://www.cnblogs.com/jerryjiang/p/17435182.html