题面
给定一个小于 \(1\) 的正实数 \(r\) 和一个正整数 \(n\)。 要求在满足 \(0≤p≤q≤n\) 和 \(\gcd(p,q)=1\) 的前提下，找到使 \(|r-\frac{q}{p}|\) 最小的二元组 \((p,q)\) 。 如果存在多个这样的二元组 \((p,q)\)，输出 \(\frac{q}{p}\) 值最小的那个。
数据范围：\(1\le n \le 10^{10}\)，\(r\in (0,1)\) 且最多包含 18 位有效数字。
题解
一个 Stern–Brocot 树 的题，记录一下这种算法。
详细解说见OI-wiki ，这里只有简单说明：
SB树从 \((\frac 01,\frac10)\) 开始，记当前节点为 \((\frac ab,\frac cd)\)，其左右儿子节点分别是 \((\frac ab,\frac {a+c}{b+d})\) 和 \((\frac {a+c}{b+d},\frac cd)\) 。
这样构建出来的SB树就有以下性质：
- 单调性：在每一层的序列中，真分数是单调递增的。
- 最简性：序列中的分数（除了 \((\frac01,\frac10)\) ）都是最简分数。
构建：
-
当然可以直接构建，复杂度为 \(O(n)\);
void build(int a = 0, int b = 1, int c = 1, int d = 0, int level = 1) { int x = a + c, y = b + d; // ... output the current fraction x/y // at the current level in the tree build(a, b, x, y, level + 1); build(x, y, c, d, level + 1); } -
如果只需要查询其中的一个分数在哪个位置，则有以下做法：
记一次转弯表示：\(x\to x\) 的左儿子 \(\to x\) 左儿子的右儿子（先右后左也是的）。
那么我们保证从根节点到 \(\frac nm\) ，转弯次数为 \(O(\log n)\)，原理大致为转弯的操作对数值的影响类似斐波那契数列。
这样我们就可以这么构建：求出最大的 \(k\) ，使 \(\frac{a+kc}{b+kd}\le \frac{n}{m}\) ，然后进入 \((\frac{a+kc}{b+kd},\frac{c}{d})\) ，然后在对 \(\frac{c+ka}{d+kb}\) 处理...
\(k\) 是什么还是现场推吧。
现在看此题，就是在SB树上进行查找操作，注意精度问题，可以用 \((a,b)\) 的形式代替浮点数以保证精度。
？
在看ATcoder 上的时候莫名发现一个巨简单的写法，但是看不懂...
看以后会不会填坑：
int a = 0, b = 1, c = 1, d = 0, x = n, y = k;
while (y) {
int r = x / y;
x %= y;
swap(x, y);
int t = b + d * r;
if (t > m) r = (m - b) / d;
a += c * r, b += d * r;
swap(a, c);
swap(b, d);
if (t > m)break;
}
启发
- 记录一下 Stern–Brocot 树 这个算法。