BZOJ 2187 - fraction

题面

给定四个正整数 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 最小的一组解。

数据范围

1a,b,c,d1091 \le a, b, c, d \le 10^9

数据组数 T500T \le 500

数据保证一定有解。

题目链接

分析

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

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

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

正式地说,如果满足:

{cdab1c≢0(modd)cd1ab1c0(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 为解。


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

aba \le bcdc \le d ,我们可以考虑对问题进行转换:

ab<pq<cddc<qp<ba\frac{a}{b} < \frac{p}{q} < \frac{c}{d} \Leftrightarrow \frac{d}{c} < \frac{q}{p} < \frac{b}{a}

由此一来,我们可以对子问题 f(d,c,b,a)=p,qf(d, c, b, a) = \langle p’, q’ \rangle 进行求解,并在回溯的时候令 p=q,q=pp = q’, q = p’ 即可。

这样一来,我们接下来就只需要考虑 c>dc > d 的情况了。如果此时出现了上面所说的 ab\frac{a}{b}cd\frac{c}{d} 间存在正整数,那么直接回溯就好了。如果不存在,我们考虑对问题进行如下变换从而尽量缩小 aa

ab<pq<cdabab<pqab<cdabababb<pqabq<cdabdamodbb<pqabq<cdabd\begin{aligned}
& \frac{a}{b} < \frac{p}{q} < \frac{c}{d} \
& \Leftrightarrow \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 \
& \Leftrightarrow \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} \
& \Leftrightarrow \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(amodb,b,cdab,d)=p,qf(a \bmod b, b, c - d\left\lfloor \frac{a}{b} \right\rfloor, d) = \langle p’’, q’’ \rangle 求解,并在回溯的时候令 p=p+qab,q=qp = p’’ + q’’\left\lfloor \frac{a}{b} \right\rfloor, q = q’' 即可。

这就跟欧几里德算法很类似了…… 每常数步我们都可以将 aa 的规模缩小至 amodba \bmod b,故复杂度为 O(logn)\mathcal{O}(\log{n})

实现

完整参考代码

This blog is under a CC BY-NC-SA 4.0 Unported License.
Link to this article: https://blog.codgician.pw/2018/10/28/bzoj-2187/