P1458 顺序的分数 Ordered Fractions

    • 1.2K通过
    • 1.9K提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 快速排序,快排 排序 搜索 数论,数学 枚举,暴力 USACO
  • 难度 普及-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    输入一个自然数N,对于一个最简分数a/b(分子和分母互质的分数),满足1<=b<=N,0<=a/b<=1,请找出所有满足条件的分数。

    这有一个例子,当N=5时,所有解为:

    0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1

    给定一个自然数N,1<=n<=160,请编程按分数值递增的顺序输出所有解。

    注:①0和任意自然数的最大公约数就是那个自然数②互质指最大公约数等于1的两个自然数。

    输入输出格式

    输入格式:

    单独的一行一个自然数N(1..160)

    输出格式:

    每个分数单独占一行,按照大小次序排列

    输入输出样例

    输入样例#1: 复制
    5
    
    输出样例#1: 复制
    0/1
    1/5
    1/4
    1/3
    2/5
    1/2
    3/5
    2/3
    3/4
    4/5
    1/1
    

    说明

    USACO 2.1

    翻译来自NOCOW

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。