/ Vijos / 题库 /

埃及分数

埃及分数

时间限制:1秒  内存限制:256M


【问题描述】

  在古埃及,人们使用单位分数的和(形如 \(1/a\),\(a\) 是大于 0 的自然数)表示一切有理数。 如:2/3=1/2+1/6,但不允许2/3=1/3+1/3,因为加数中有相同的。对于一个分数 \(a/b\),表示方法有很多种,但是哪种最好呢?首先,加数少的比加数多的好;其次,加数个数相同的,最小的分数越大越好,若最小的分数相同,则次小的分数越大越好,……依次类推。例如:
  19/45 = 1/3 + 1/12 + 1/180
  19/45 = 1/3 + 1/15 + 1/45
  19/45 = 1/3 + 1/18 + 1/30
  19/45 = 1/4 + 1/6 + 1/180
  19/45 = 1/5 + 1/6 + 1/18
  最好的是最后一种,因为1/18比1/180,1/45,1/30,1/180都大。
  现在给出 \(a,b\),编程计算最好的表达方式。

【输入格式】

  两个正整数:\(a\) 和 \(b\)。

【输出格式】

  若干个数,自小到大排列,依次是单位分数的分母。

【输入输出样例】

 Input

19 45

 Output

5 6 18

【数据说明】

  对于所有数据保证 \(0<a<b<1000\)。

【来源】

  Mr.he

信息

ID
2442
难度
(无)
分类
搜索 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
被复制
1
上传者