题解 P1298 最接近的分数
251Sec
·
·
题解
看了下这个题的题解区。
地铁，老人，手机.jpg。
（我怎么一个都看不懂啊啊啊我好菜）
所以下面介绍一下我的做法。
引入：一道小学奥数题
求最小的 p, q 使得 \dfrac{30}{7} < \dfrac{p}{q} < \dfrac{34}{7}。
你不觉得这个假分数看着很难受吗？
处理掉它：\dfrac{2}{7} < \dfrac{p-4q}{q} < \dfrac{6}{7}。
然后呢？
聪明的你已经知道了。求倒数！令 p-4q=r。
我们再处理掉假分数：
$\dfrac{1}{6} < \dfrac{q-r}{r} < \dfrac{5}{2}$。
我们发现此时小于号两边分别是一个真分数和一个假分数。可以直接令 $q-r=1$，$r=1$。
然后我们再逆推回去，可以得到 $p=9,q=2$。
可以发现，类似的方法可以用于求解 $\dfrac{a}{b} < \dfrac{p}{q} < \dfrac{c}{d}$ 中使 $p, q$ 最小的问题。
Code：
```cpp
void sol(ll a, ll b, ll c, ll d, ll& p, ll& q)
{
if (a < b && c > d) {
p = 1;
q = 1;
} else {
sol(d % c, c, b - d / c * a, a, q, p);
q += d / c * p;
}
}
```
## 正式开始
可以发现，上面的方法需要频繁取倒数，所以对精度要求比较高，因此我们将输入的小数用分数表示。这里分母取 $10^{14}$。得到分数 $\dfrac{a}{10^{14}}$。
显然，若在距 $r$ 在 $k$ 的范围之内时，存在满足条件的 $p, q$，那么距离在 $k' > k$ 之内时，也存在满足条件的 $p, q$。找到了单调性，我们可以二分所求答案 $\dfrac{p}{q}$ 与 $r$ 的距离 $k$。
分类讨论答案大于和小于 $r$ 的情况，跑两次二分：
当答案小于 $r$， 用上述方法求满足 $\dfrac{a-k-1}{10^{14}} < \dfrac{p}{q} < \dfrac{a + 1}{10^{14}}$ 的最小 $p, q$。而 `check()` 只需判断 `p <= m && q <= n`。
同理，答案大于 $r$ 时，也可以用类似的方法。
这样我们就解决了求答案的问题。那么怎么判断答案是否唯一呢？
这个也很简单，只要枚举过程中有多个数与答案距离相同，答案就是不唯一的。这一点其他题解已经说得很清楚了。注意枚举过程中可能枚举到同一个数，这种情况是不算重复的。
浮点数有精度误差，所以要判断相差值小于一个极小值，就可以认为相等。（这好像是常识吧？）
最终复杂度 $O(\log^2r)$。
Code:
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef __int128 ll;
typedef long double ld;
class IO {
template <class T>
void write(T a)
{
if (a > 9)
write(a / 10);
putchar(a % 10 + '0');
}
public:
template <class T>
IO operator<<(T a)
{
if (a < 0) {
putchar('-');
a = -a;
}
write(a);
return *this;
}
IO operator<<(char a)
{
putchar(a);
return *this;
}
template <class T>
IO operator>>(T& a)
{
int sign = 1;
a = 0;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') {
sign = -1;
}
c = getchar();
}
while (c >= '0' && c <= '9') {
a = (a << 1) + (a << 3) + (c ^ 48);
c = getchar();
}
a *= sign;
return *this;
}
} io;
ll m, n;
ld fr;
ll a;
bool flag;
ll ansa, ansb;
ld ansd;
void sol(ll a, ll b, ll c, ll d, ll& p, ll& q)
{
if (a < b && c > d) {
p = 1;
q = 1;
} else {
sol(d % c, c, b - d / c * a, a, q, p);
q += d / c * p;
}
}
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
ll max(ll a, ll b)
{
return a > b ? a : b;
}
int main()
{
io >> m >> n;
scanf("%Lf", &fr);
a = fr * 1e14;
ansa = 0;
ansb = 1;
ansd = fr;
ll l = 1, r = 1e16;
flag = true;
while (l <= r) {
ll mid = (l + r) / 2;
ll p, q;
sol(a - 1, 1e14, a + mid + 1, 1e14, p, q);
if (p <= m && q <= n) {
r = mid - 1;
if (fabs(fabs(a / 1e14 - 1.0 * p / q) - ansd) < 1e-16 && (ansa != p || ansb != q)) {
flag = false;
}
else if (fabs(a / 1e14 - 1.0 * p / q) < ansd) {
ansa = p, ansb = q, ansd = fabs(a / 1e14 - 1.0 * p / q);
flag = true;
}
}
else {
l = mid + 1;
}
}
l = 1, r = 1e16;
while (l <= r) {
ll mid = (l + r) / 2;
ll p, q;
sol(max(a - mid - 1, 0), 1e14, a + 1, 1e14, p, q);
if (p <= m && q <= n) {
r = mid - 1;
if (fabs(fabs(a / 1e14 - 1.0 * p / q) - ansd) < 1e-16 && (ansa != p || ansb != q)) {
flag = false;
}
else if (fabs(a / 1e14 - 1.0 * p / q) < ansd) {
ansa = p, ansb = q, ansd = fabs(a / 1e14 - 1.0 * p / q);
flag = true;
}
} else {
l = mid + 1;
}
}
if (flag)
io << ansa << '/' << ansb;
else
puts("TOO MANY");
return 0;
}
```
## 一个问题
我们一直在说让 $p, q$ 最小。那么，是否最小化 $p$ 等价于最小化 $q$ 呢？
是的。
证明：
若存在满足条件的最简分数 $\dfrac{x}{y}$，使得 $x>p, y < q$。那么 $\dfrac{x}{y} < \dfrac{x}{q} < \dfrac{p}{q}$。显然 $\dfrac{x}{q}$ 更优。
若存在满足条件的最简分数 $\dfrac{x}{y}$，使得 $x<p, y > q$。那么 $\dfrac{x}{y} < \dfrac{p}{y} < \dfrac{p}{q}$。显然 $\dfrac{p}{y}$ 更优。
因此最优解的分子和分母同时最小。
## 双倍经验
[P5179](https://www.luogu.com.cn/problem/P5179)