usaco-2.1.2 顺序的分数

题目描述

输入自然数 $N$ （ $1 \le N \le 160$ ），按从小到大输出所有分母不超过 $N$ 的既约真分数，每行一个。

样例输入 5，输出 0/1、1/5、1/4、1/3、2/5、1/2、3/5、2/3、3/4、4/5、1/1 各占一行。

思路

枚举分母 $b$ 和分子 $a$ ，用 $\gcd$ 约分后丢进有序集合去重，就得到全部最简分数。排序必须按分数值比较（交叉相乘 $ad$ 与 $cb$ ），不能对分子分母元组做字典序比较。分子从 $0$ 开始枚举才能让 0/1 排在开头。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 03:19
# update_at: 2026-10-01 03:19

import sys
from math import gcd


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)

    # 枚举所有 (分子, 分母)，gcd 归约去重；0 只保留 0/1，避免 0/2..0/n 混进来。
    # tuple 直接比较是先比分子的，必须按分数值 a/b 排序。
    fracs = sorted(
        {(a // gcd(a, b), b // gcd(a, b)) for b in range(1, n + 1) for a in range(b + 1)},
        key=lambda t: t[0] / t[1],
    )
    sys.stdout.write(''.join(f'{a}/{b}\n' for a, b in fracs))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 09:40
 * update_at: 2026-10-06 09:40
 */
// main.cpp：枚举分母不超过 N 的分数，gcd 约分去重后按分数值升序输出。
#include <cstdio>
#include <set>
#include <vector>
#include <algorithm>

typedef long long ll;

std::set<std::pair<ll, ll> > unique_frac;  // 约分后的 (分子, 分母) 集合，天然去重
std::vector<std::pair<ll, ll> > fractions; // 去重后的最简分数，排序后输出

// 求 x 与 y 的最大公约数，用于把 a/b 约成最简分数。
ll gcd_ll(ll x, ll y) {
    while (y != 0) {
        ll temp = x % y;
        x = y;
        y = temp;
    }
    return x;
}

// 比较函数：a/b < c/d 等价于 a*d < c*b，用交叉相乘避免浮点误差。
bool frac_less(std::pair<ll, ll> x, std::pair<ll, ll> y) {
    return x.first * y.second < y.first * x.second;
}

int main() {
    ll n;
    std::scanf("%lld", &n);

    // 枚举 b 从 1 到 n、a 从 0 到 b，把每个分数约分后丢进集合去重。
    ll b, a;
    for (b = 1; b <= n; b++) {
        for (a = 0; a <= b; a++) {
            ll g = gcd_ll(a, b);
            unique_frac.insert(std::make_pair(a / g, b / g));
        }
    }

    for (std::set<std::pair<ll, ll> >::iterator it = unique_frac.begin(); it != unique_frac.end(); ++it) {
        fractions.push_back(*it);
    }
    std::sort(fractions.begin(), fractions.end(), frac_less);

    for (std::vector<std::pair<ll, ll> >::iterator it = fractions.begin(); it != fractions.end(); ++it) {
        std::printf("%lld/%lld\n", it->first, it->second);
    }
    return 0;
}

usaco-2.1.2 顺序的分数

目录

题目描述

思路

参考代码