多組詢問，每次給出 $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，不知道咋解決
個性簽名：時間會解決一切