分别在 随机 (11)，中点（35，37，38，44，46），构造（49，50） 处 Wrong Answer（前面是 AtCoder 的数据编号）。

做法简述：

构造 Stein-Brocot 树 $(T, \oplus)$。注意到

$$\dfrac ab \oplus \underset{k}{\underbrace{\dfrac cd \oplus \dots \oplus \dfrac cd}} = \dfrac{a+kc}{b+kd}.$$

所以，$\dfrac{a+kc}{b+kd} = \lambda$ 被一个一次方程控制。解出这个 $k$ 代表 $R^k$。同理可以得出 $L^k$ 的情况。 再次注意到：

$$\begin{aligned} [p, q] \to [p \oplus q, q] \to [p \oplus q, p \oplus q \oplus q] \end{aligned}$$

时，右端点分母加倍。由于右端点分母不能超过 $n$，故 $LR$ 交替次数不超过 $\mathrm O(\log n)$。 现在在 Stein-Brocot 树上搜寻 $\lambda$，每次选择是 $L^k$ 还是 $R^k$，而一次 $L^k$ 或 $R^k$ 的计算可以 $\mathrm O(1)$ 完成。

现在在这些点上，获得 WA。目前有两种可能的错误：

• 精度不够。
• 并没有保证如果 $\varepsilon$ 最小时，$\dfrac pq < \lambda$。

给出代码：

#include <bits/stdc++.h>
using namespace std;

using ll = __int128;
using lf = long double;

bool eq(lf a, lf b) { return !(abs((a - b) / max(abs(a), abs(b))) >= 1e-12); }

int main() {
    lf x, eps = 1;
    cin >> x;
    ll a = 0, b = 1, c = 1, d = 0, ansA, ansB;
    long long N;
    cin >> N;
    for (;;) {
        // cout << a << " " << b << " " << c << " " << d << endl;
        ll kr = floor((x * b - a) / (c - x * d)),
           kl = floor((c - x * d) / (x * b - a)), e, f;
        if (b) kl = min((N - d) / b, kl);
        if (d) kr = min((N - b) / d, kr);
        if (kl) {
            // cout << "L " << (long long)kl << endl;
            e = kl * a + c, f = kl * b + d;
            c = e;
            d = f;
        } else if (kr) {
            // cout << "R " << (long long)kr << endl;
            e = a + kr * c, f = b + kr * d;
            a = e;
            b = f;
        } else
            break;
        if (f > N) break;
        if (abs((lf)e / f - x) < eps && !eq(abs((lf)e / f - x), eps))
            ansA = e, ansB = f, eps = abs((lf)e / f - x);
        if (eq(abs((lf)e / f - x), eps) && e < f * x) ansA = e, ansB = f;
    }
    if (eq(abs((lf)(ansA - 1) / ansB - x), eps)) ansA--;
    cout << (long long)ansA << " " << (long long)ansB << endl;
}