题解 P1458 【顺序的分数 Ordered Fractions】

· · 题解

发现很多题解都是枚举+sort做的……

这里介绍一种方法：分治。

我们假设有两个分数a/b<c/d。我们要从小到大输出这个区间上满足题意的分数。

我们令m = a + c, n = b + d。可证明a / b < m / n < c / d. （交叉相乘即可证明）

并且我们可以证明这些分数都是最简的。（并不会证明233）

那么我们只需要对m/n的左右两个区间继续分治，即可按顺序得到所求分数。

然后这种方法来源于做过的一道 分数树 的题。这里贴个链接：http://www.docin.com/p-1022648660.html

(2019.7.11 upd) 对以上部分内容进行补充：

可以发现这样分治过程形成了一棵树，这样的树叫做 Stern-Brocot Tree。这棵树能够不重不漏的表示所有有理数（既约分数）。

构造方法是：第一层是 \frac{0}{1} 和 \frac{1}{0}，每次在两个相邻分数 \frac{m}{n}, \frac{m'}{n'} 之间插入 \frac{m + m'}{n + n'}，并把新生成的节点插入下一层中。

则有如下性质：对于任意构造阶段的两个相邻分数 \frac{m}{n}, \frac{m'}{n'}，有 m'n - mn' = 1，可以用归纳法证明得到。

接着由这个性质可以证明每个有理数都存在：假设 \frac{a}{b} 不在任意一层序列中，则对于每一层找到最接近 \frac{a}{b} 的两个分数 \frac{m}{n} \lt \frac{a}{b} \lt \frac{m'}{n'}，则有

an - bm \ge 1, bm' - an' \ge 1

于是：

(an - bm)(m'+n') + (bm' - an')(m+n) \ge m+n+m'+n'

又由 m'n - mn' = 1 得：

a+b \ge m + n + m' + n'

而右边可以取到 \infty，矛盾。这样就证明了每个有理数都存在于这棵树中。

接着可以发现树中每个有理数是不重复的，因为 \frac{a}{b} \lt \frac{a + a'}{b + b'} \lt \frac{a'}{b'}。

这道题只需要从 \frac{0}{1} 和 \frac{1}{1} 中间夹的子树分治即可。

然后上代码（Pas代码下面几篇题解里有，这里贴C++的）

#include <iostream>
#include <cstdio>

using namespace std;

int    N;

void DFS(const int& l1, const int& l2, const int& r1, const int& r2)
{
    if(l2 > N || r2 > N)
        return;

    DFS(l1, l2, l1 + r1, l2 + r2);
    if(l2 + r2 <= N)
        printf("%d/%d\n", l1 + r1, l2 + r2);
    DFS(l1 + r1, l2 + r2, r1, r2);
}

int main()
{
    cin >> N;

    printf("0/1\n");
    DFS(0, 1, 1, 1);
    printf("1/1\n");

    return 0;
}