【题解】【P5179 Fraction】

· · 题解

前言（闲话）

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

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

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

求 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'，满足最优子结构