51Nod1187 寻找分数

Vexoben

Sep 2, 2018

It takes 2 minutes to read this article.

题目链接：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;
}