自动搬运

查看原文

来自洛谷，原作者为

	derta 这个家伙很勤劳，只留下了一堆坑

搬运于2025-08-24 22:07:57，当前版本为作者最后更新于2021-12-11 22:01:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

前言（闲话）

我在题解区看到这样一句话：

本题乍一看很简单：这不就是小学数学题吗……

其实这位老哥说得对，这确实是一道小学奥数题。那时我所见的题面是这样的：

求 $p+q$ 最小的整数 $(p,q)$ 使得 $\dfrac{p}{q}$ 前几位为 $3.14$

它相当于 $a=314,b=100,c=315,d=100$ 的情况，并且正解也是迭代。当时觉得这个做法很美妙，遂将其改写成 OI 题的形式，并写了（错误的）std。这也就成为了我题库中的第一道题。

题解

建议：看一步之后自己向下思考，不会了再继续看

不妨考虑一个例子：

$$\frac{314}{100}<\frac{p}{q}<\frac{315}{100}$$

首先看这个假分数就不顺眼，统一减 $3$！

$$\frac{14}{100}<\frac{p-3q}{q}<\frac{15}{100}$$

看这个分子上的 $p-3q$ 也不顺眼，换元，令 $r=p-3q$！

$$\frac{14}{100}<\frac{r}{q}<\frac{15}{100}$$

之后就又回到了题目的形式，但是两边变成了真分数，怎么办？

这是关键的一步，请务必自行思考。

（其实有些初联题也用到了类似的套路，可能让 MOer 来做更好一点）

答案是：取倒数。由此得到

$$\frac{100}{15}<\frac{q}{r}<\frac{100}{14}$$

之后用类似的方法迭代：

$$\frac{10}{15}<\frac{q-6r}{r}<\frac{15}{14}$$

等等，一边是真分数，一边是假分数，这又该怎么办？

其实已经结束了。可以发现，$q-6r=1,r=1$ 是最优解，回溯：

$$q-6r=1 \Longrightarrow q=7$$ $$p-3q=r \Longrightarrow p=22$$

至此，我们得出答案。

但是还有关键性的一步没有解决：该问题是否满足最优子结构？证明附于文末，请读者自行思考。

至于代码，有些题解分类比较繁琐，其实可以像求 $\gcd$ 一样合并在一起。时间复杂度的分析也与 $\gcd$ 相同，单次 $O(\log n)$。

void gcd(int a, int b, int& p, int& q, int c, int d) {
	if(a < b && c > d) //边界情况
		p = 1, q = 1;
	else {
		gcd(d%c, c, q, p, b - (d/c)*a, a); //真分数-（取倒数）->假分数-（化简）->真分数。类似gcd，如果进来的是假分数会取倒数变成真分数，不会死循环
		q += (d/c)*p; //回溯时反解出q
	}
}

证明：当 $q$ 尽量小时，$p$ 也会随之变小。若不满足最优子结构，设换元时 $p=kq+r$，$(q,r)$ 为可以使 $p$ 最优的解，最优子结构为 $(q',r')$，有 $q' \leq q,r'\geq r$（否则 $(q,r)$ 显然不是最优解），故

$$\frac{a}{b}<\frac{r}{q}\leq\frac{r}{q'}\leq\frac{r'}{q'}<\frac{c}{d} $$

故 $q=q'$，所以 $r=r'$，满足最优子结构