ABC408G sol: stern-brocot

arrow_king · 2025-06-03 15:49:10 · 题解

分数比大小题怎么能没有 Stern-Brocot 树的题解呢？

Stern-Brocot 树是一个维护所有最简分数的优雅结构。

假设我们有一个序列，初始含有两个分数 \dfrac01 和 \dfrac10。（这里 \dfrac10 严格来说不能看做分数，这里认为是 +\infty 的表示。）

每一轮迭代，我们取序列中所有相邻的分数 \dfrac ab 和 \dfrac cd，将一个新的分数 \dfrac{a+c}{b+d} 插入到其中。

比如，第二轮迭代后序列如下：

如果把插入新分数看做一个二叉树的结构，就可以抽象出 Stern-Brocot 树的结构：（图来自 oi-wiki）

这棵树有以下性质：（证明见 oi-wiki）

1. 每次迭代后的分数序列都是单调递增的。
2. 所有分数都是最简分数。
3. 包含所有的正分数。

因为 Stern-Brocot 树是二叉搜索树，因此我们显然可以在上面进行二分搜索来查找到目标分数。由于向左走分数一定减小，向右走分数一定增大，因此我们只需要维护当前访问的区间是 \left(\dfrac ab,\dfrac cd\right)，比较 \dfrac{a+c}{b+d} 与目标分数的大小关系即可。

查找 \dfrac pq 时这样朴素的搜索复杂度为 O(p+q)，无法接受。考虑到复杂度高的原因是在当前区间的界与目标分数较近时收敛缓慢，会重复向左/右跳很多次。考虑 O(1) 求出向一个方向跳的次数。驾驶向左跳 t 次，当前分数变为 \dfrac{a+tc}{b+td}。解方程 \dfrac{a+tc}{b+td}<\dfrac pq 即可。向右跳同理。

考虑到一次换方向会使得分子分母各至少乘 2，因此这样跳的复杂度是 O(\log(p+q))。

回到这个题，要求找到 \dfrac ab<\dfrac pq<\dfrac cd，我们只需要在 \dfrac pq>\dfrac ab 的条件下满足 \dfrac pq<\dfrac cd 即可，因为分母按照深度递增，我们只需要保证 \dfrac pq 是满足条件的情况下最靠边的一个（也就是同向跳跃最少的一个）即可。

单次查询的复杂度是 O(\log a+\log b+\log c+\log d)，可以通过。

因为值域有点大，要写 __int128 才能通过。

pll ans;
i128 A,B,C,D;
il bool Less(i128 a,i128 b,i128 c,i128 d) {return a*d<b*c;}
il void solve(i128 a,i128 b,i128 c,i128 d) {
    i128 n=a+c,m=b+d;
    if(Less(A,B,n,m)&&Less(n,m,C,D)) return ans=mkp(n,m),void();
    if(!Less(A,B,n,m)) {
        i128 t=(m*A-n*B)/(c*B-d*A);
        solve(n+t*c,m+t*d,c,d);
    }
    else {
        i128 t=(m*C-n*D)/(a*D-b*C);
        solve(a,b,n+t*a,m+t*b);
    }
}