bzoj2187: fraction——类欧几里得

题意

多组询问，每次给出 $a, b, c, d$，求满足 $\frac{a}{b}  < \frac{p}{q} < \frac{c}{d}$ 的所有二元组 $(p, q)$ 中 $p$ 为第一关键字，$q$ 为第二关键字排出来的字典序最小的那一对。

分析

设计函数 $f(a,b,p,q,c,d)$.

按照题目中保证 $q$ 最小的要求考虑该函数的几个边界：

1. $\left \lfloor \frac{a}{b} \right \rfloor-1 \leq \left \lceil \frac{c}{d} \right \rceil-1$，这个时候 $p = \left \lfloor \frac{a}{b} \right \rfloor+1, q=1$ 时字典序最小

2. $a=0$ 时，这个时候 $0 < \frac{p}{q} < \frac{c}{d} \Rightarrow q > \frac{dp}{c}$，显然 $p=1, q=\left \lfloor \frac{c}{d} \right \rfloor+1$ 时字典序最小

然后考虑辗转相除缩小问题规模：

1. $a > b\ or \ c > d$：原式等价于：$\frac{a\%b}{b} < \frac{p}{q}-\left \lfloor \frac{a}{b} \right \rfloor < \frac{c}{d}-\left \lfloor \frac{a}{b} \right \rfloor$

即：$f(a, b, p, q, c,d) = f(a \% b, b, p, q, c-{\left \lfloor \frac{a}{b} \right \rfloor}d), p+= {\left \lfloor \frac{a}{b} \right \rfloor}q$.

2. 

bzoj2187: fraction——类欧几里得

原文：https://www.cnblogs.com/lfri/p/11660872.html