题解：Good Bitstrings 计数

问题转化

函数 gen_string(a,b) 生成一个长度为 $a+b$ 的二进制串，其中有 $a$ 个 0 和 $b$ 个 1。
生成规则：维护 $(ia, ib)$ 分别表示已生成的 0 和 1 的个数，每次比较 $\frac{ia}{a}$ 和 $\frac{ib}{b}$，选择比值较小的一侧添加对应字符（相等时加 0）。

好串：存在 $(x,y)$ 使得 s = \texttt{gen_string}(x,y)。

给定 $A,B$，求 \texttt{gen_string}(A,B) 的所有前缀中好串的个数。

关键性质

生成过程可看作在平面 $(ia, ib)$ 上从 $(0,0)$ 到 $(a,b)$ 的路径，每次向右（0）或向上（1），选择规则是比较 $\frac{ia}{a}$ 和 $\frac{ib}{b}$，即比较斜率 $ib/ia$ 与 $b/a$（但 $ia=0$ 时特判）。

好前缀对应于路径上某个点 $(c,d)$ 恰好是某个生成过程 $(x,y)$ 的终点，且从 $(0,0)$ 到 $(c,d)$ 的路径与用 $(x,y)$ 生成的路径一致。

生成路径的几何解释

设当前点 $(p,q)$，若 $\frac{p}{x} \le \frac{q}{y}$ 则向右走，否则向上走。

这等价于在直线 $y = \frac{y}{x} \cdot x$ 下方（或线上）时向右走，上方时向上走。

因此路径是沿着斜率 $y/x$ 的直线“交替”前进的格点路径。

好前缀的特征

对于前缀 $(c,d)$，若它是好的，则存在 $(x,y)$ 使得 \texttt{gen_string}(x,y) 的长度为 $c+d$，且生成的串与 $A,B$ 的前缀相同。

这要求 $(c,d)$ 满足：从 $(0,0)$ 到 $(c,d)$ 的路径与用 $(x,y)$ 生成的路径一致，且该路径也是从 $(0,0)$ 到 $(x,y)$ 的唯一生成路径（根据规则）。

已知结论

好前缀 $(c,d)$ 对应 $(x,y)$ 需满足：

• $(c,d)$ 在直线 $y = \frac{B}{A} \cdot x$ 的路径上
• $(x,y)$ 是某个 Farey 序对（即 $\gcd(x,y)=1$）
• 且 $(c,d)$ 是 $(x,y)$ 的生成路径上的某个点

实际上，好前缀 $(c,d)$ 必须满足存在 $(x,y)$ 使得 $(c,d)$ 是 $(x,y)$ 的生成路径上的一点，且从 $(0,0)$ 到 $(c,d)$ 的子路径与用 $(A,B)$ 生成时一致。

Stern–Brocot 树

生成规则本质是 Stern–Brocot 树上的行走：
每个分数 $y/x$ 对应一个生成串，路径是沿 SB 树从 $0/1$ 到 $y/x$ 的路径。

好前缀对应 SB 树上某个节点 $y/x$ 的路径前缀，且该前缀也是从 $0/1$ 到 $B/A$ 的路径的一部分。

因此问题转化为：在 SB 树上从 $0/1$ 到 $B/A$ 的路径上，有多少个节点 $y/x$ 使得从根到该节点的路径是从 $0/1$ 到 $B/A$ 的路径的前缀。

算法步骤

1. 将 $B/A$ 化为最简分数（除以 $\gcd$）。
2. 在 Stern–Brocot 树上模拟从 $0/1$ 到 $B/A$ 的路径：
   • 左子节点 $(y_L/x_L)$，右子节点 $(y_R/x_R)$
   • 比较 $B/A$ 与当前节点的分数，决定向左/右走
3. 统计路径上所有节点（包括端点）的个数，即为答案。

复杂度

SB 树深度为 $O(\log(A+B))$，每步比较用分数避免浮点误差（交叉相乘）。

由于 $A,B \le 10^{18}$，使用 __int128 比较。

总复杂度 $O(T \log (A+B))$。

实现细节

• 初始左分数 $L = (0,1)$，右分数 $R = (1,0)$。
• 当前节点 $M = (L_y+R_y, L_x+R_x)$。
• 比较 $B/A$ 与 $M_y/M_x$： 若 $B * M_x < A * M_y$ 则向左走（$R \leftarrow M$） 否则向右走（$L \leftarrow M$）
• 每走一步计数 $+1$，直到 $M = (B,A)$ 的最简形式。

答案 = 路径节点数（包括起点 $0/1$ 和终点 $B/A$）。

最终答案

输出路径长度即可。