Vexoben
Sep 2, 2018
题目链接：51Nod1187 寻找分数
（刷新以获取数学公式）
题解
非常高妙的一道题……
首先要发现一个结论：\(q\)最小等价于\(p\)最小。
证明比较容易就略过了。
然后考虑几种特殊情况：
1、若 \(a = 0\)， 那么令 \(p = 1\)， 求出 \(q\) 得到答案；
2、若 \(\frac{a}{b} 与 \frac{c}{d}\)整数部分不同, 令 \(q = 1\)，求出 \(p\)得到答案；
3、否则令\(t = a / b\)，那么求出\((a\, mod \, b, b, c \, mod \,d, d )\)的答案再加上 \(t\)就是答案。
如果出现了第三种情况，可以翻转分子分母，得到\(\frac{b}{a} > \frac{q}{p} > \frac{d}{c}\)，向下递归即可。
事实上在部分情况下，情况2的分母需要设置为2，要讨论一下，见代码。
#include<bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int, int>
#define int long long
using namespace std;
const int N = 1e5 + 10;
pii dfs(int a, int b, int c, int d) {
if (!a) {
int x = d / c + 1;
return make_pair(1, x);
}
if (a / b != c / d) {
int x = a / b + 1;
if (c <= d * x) {
x = a / b * 2 + 1;
return make_pair(x, 2);
}
else return make_pair(x, 1);
}
int s = a / b;
a %= b; c %= d;
pii t = dfs(d, c, b, a);
swap(t.fi, t.se);
t.fi += s * t.se;
return t;
}
void Solve() {
int a, b, c, d;
cin >> a >> b >> c >> d;
pii ans = dfs(a, b, c, d);
cout << ans.fi << '/' << ans.se << endl;
}
signed main() {
int T; cin >> T;
while (T--) Solve();
return 0;
}