自动搬运

查看原文

来自洛谷，原作者为

	浮尘ii **

搬运于2025-08-24 21:25:18，当前版本为作者最后更新于2017-07-04 20:30:51，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

发现很多题解都是枚举+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'}$，则有

于是：

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

而右边可以取到 $\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;
}