题目大意
求最简分数 $p/q$ 满足
$$ \frac{a}{b} < \frac{p}{q} < \frac{c}{d} $$
若有多组解，输出 $q$ 最小的；仍有多组解，输出 $p$ 最小的一组。
分析
分类讨论：
- 首先当 $\lfloor a/b \rfloor + 1 \leqslant \lceil c/d \rceil - 1$ 时，说明两个数之间存在一个整数，直接返回 $p = 1, q = \lfloor a / b \rfloor + 1$ 即可。
- 其次当 $a = 0$ 时，直接解得 $p = 1, q = \lfloor d / c \rfloor + 1$。
- 当 $a < b$ 时，这意味着我们无法直接求解。考虑翻转，转化问题为 $$ \frac{d}{c} < \frac{q}{p} < \frac{b}{a} $$ 递归即可。
- 当 $a > b$ 时，考虑求解 $$ \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 $$ 也是递归即可，还原出结果以后返回。
唯一需要确认的就是，翻转后仍是最优解，考虑反证。
设存在 $p_0 \geqslant p$ 且 $q_0 < q$ 使得 $p_0/q_0$ 在翻转前不是最优解，但是翻转后是最优解。从而有 $$ \frac{d}{c} < \frac{p_0}{q_0} < \frac{p_0}{q} \leqslant \frac{p}{q} < \frac{b}{a} $$ 即 $p_0/q$ 是翻转前的更优解，与 $p/q$ 是最优解矛盾。
void solve(ll a, ll b, ll &p, ll &q, ll c, ll d) {
ll x = a / b, y = (c - 1) / d;
if (x < y) {
p = x + 1, q = 1;
} else if (a == 0) {
p = 1, q = d / c + 1;
} else if (a < b) {
solve(d, c, q, p, b, a);
} else {
solve(a - b * x, b, p, q, c - d * x, d);
p += q * x;
}
}