题面

给定四个正整数 a,b,c,da, b, c, d ，试求最简正分数 pq\frac{p}{q} ，满足：

ab<pq<cd \frac{a}{b} < \frac{p}{q} < \frac{c}{d}

若有多组解，取 qq 最小的一组解；若仍有多组解，取 pp 最小的一组解。

数据范围：1≤a,b,c,d≤1091 \le a, b, c, d \le 10^9 ，数据组数 T≤500T \le 500 ，保证一定有解。

题目链接：BZOJ 2187: fraction

分析

我们记原问题的解为 f(a,b,c,d)=⟨p,q⟩f(a, b, c, d) = \langle p, q \rangle 。

我们先来讨论两种可以直接得出答案的情况。

首先，如果 ab\frac{a}{b} 和 cd\frac{c}{d} 间存在正整数，那么显然取 q=1q = 1 。

正式地说，如果满足：

{⌊cd⌋−⌊ab⌋≥1c≢0(modd)cd−1−⌊ab⌋≥1c≡0(modd) \begin{cases} \left\lfloor \frac{c}{d} \right\rfloor - \left\lfloor \frac{a}{b} \right\rfloor \ge 1 & c \not\equiv 0 \pmod d \\ \frac{c}{d} - 1 - \left\lfloor \frac{a}{b} \right\rfloor \ge 1 & c \equiv 0 \pmod d \end{cases}

那么我们取 p=⌊ab⌋+1,q=1p = \left\lfloor \frac{a}{b} \right\rfloor + 1, q = 1 为解。

其次，如果 a=0a = 0 （虽然本题中不会直接出现这一情况，但我们需要解决的子问题中可能会出现），那么很显然我们可以取 p=1,q=⌊cd⌋+1p = 1, q = \left\lfloor \frac{c}{d} \right\rfloor + 1 为解。

对于剩下不能直接得出答案的情况，我们可以考虑将问题逐步转化至上面可直接得解的情况从而递归地求解。

若 a≤ba \le b 且 c≤dc \le d ，我们可以考虑对问题进行转换：

ab<pq<cd⇒dc<qp<ba \frac{a}{b} < \frac{p}{q} < \frac{c}{d} \Rightarrow \frac{d}{c} < \frac{q}{p} < \frac{b}{a}

我们对子问题 f(d,c,b,a)=⟨p′,q′⟩f(d, c, b, a) = \langle p', q' \rangle 进行求解，并在回溯的时候令 p=q′,q=p′p = q', q = p' 即可。

接下来我们就只需要考虑 c>dc > d 的情况了。如果此时 ab\frac{a}{b} 和 cd\frac{c}{d} 间存在正整数，那么直接回溯即可。如果不存在，考虑对问题进行如下变换从而尽量缩小 aa ：

ab<pq<cd⇒ab−⌊ab⌋<pq−⌊ab⌋<cd−⌊ab⌋⇒a−b⌊ab⌋b<p−q⌊ab⌋q<c−d⌊ab⌋d⇒a mod bb<p−q⌊ab⌋q<c−d⌊ab⌋d \begin{aligned} & \frac{a}{b} < \frac{p}{q} < \frac{c}{d} \\ & \Rightarrow \frac{a}{b} - \left\lfloor \frac{a}{b} \right\rfloor < \frac{p}{q} -\left\lfloor \frac{a}{b} \right\rfloor < \frac{c}{d} - \left\lfloor \frac{a}{b} \right\rfloor \\ & \Rightarrow \frac{a - b\left\lfloor \frac{a}{b} \right\rfloor}{b} < \frac{p - q\left\lfloor \frac{a}{b} \right\rfloor}{q} < \frac{c - d\left\lfloor \frac{a}{b} \right\rfloor}{d} \\ & \Rightarrow \frac{a \bmod b}{b} < \frac{p - q\left\lfloor \frac{a}{b} \right\rfloor}{q} < \frac{c - d\left\lfloor \frac{a}{b} \right\rfloor}{d} \\ \end{aligned}

由此对子问题 f(a mod b,b,c−d⌊ab⌋,d)=⟨p′′,q′′⟩f(a \bmod b, b, c - d\left\lfloor \frac{a}{b} \right\rfloor, d) = \langle p'', q'' \rangle 求解，并在回溯的时候令 p=p′′+q′′⌊ab⌋,q=q′′p = p'' + q''\left\lfloor \frac{a}{b} \right\rfloor, q = q'' 即可。

这就跟欧几里德算法很类似了…… 每常数步我们都可以将 aa 的规模缩小至 a mod ba \bmod b ，故复杂度为 O(log⁡n)\mathcal{O}(\log{n}) 。不过为了防止中间爆 int64 我们在运算过程中可以约一下分，这样复杂度就变成了 O(log⁡2n)\mathcal{O}(\log^2{n}) 。

最后附上我的 代码 以供参考。