多组询问，每次给出 $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. $a \leq b \ and \ c \leq d$：原式等价于：$\frac{d}{c} < \frac{q}{p} < \frac{b}{a}$.
即：$f(a,b,p,q,c,d) = f(d,c,q,p,b,a)$，这样就回到了第一步。
View Code
给出两个非负有理数 $A, B$（$A < B$），你的任务是发现一个分数介于A和B，在这个区间内可能有许多分数，请输出分子加分母和最小的分数。
分析：
首先，解决输入问题，无线循环小数很容易转换成分数。
因为0.[1]=1/9, 0.0[1]=1/99, 0.00[1]=1/999...
将小数分成括号部分和非括号部分即可。
问题转换成求 $\frac{a}{b} < \frac{p}{q} < \frac{c}{d}$，且 $p+q$ 最小。
可以推导出 $p$ 最小时，$p+q$ 就最小，于是套类欧几里得模板即可。
//交上去会MLE，不知道咋解决
个性签名：时间会解决一切