传统题 1000ms 256MiB

单分子分数

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

背景

单分子分数也称为古埃及分数,即分子为1的分数,比如1/5、1/7。而对于非单分子分数,古埃及人也可以巧妙地运用单分子分数进行表示。兰德纸草书的第一页就有一个表格,上面记录了如何用单分子分数来表达分子是2的分数。表达式如下:2/5=1/3+1/15,2/11=1/6+1/66,2/29=1/24+1/58+1/174+1/232,记录的最后一个分数为2/101。

古埃及人为何如此钟意单分子分数呢?世人有很多猜想,有人觉得当时的数学就是为了满足日常生活和生产需求,还谈不上数学研究,可能单分子分数的发明就是为了对物资进行平均分配。比如8个人平均分配7个面包时,就可以用古埃及分数来解决。7/8可以用古埃及分数表示为7/8=1/2+1/4+1/8。先取4个面包,每个面包平均切成2等份,合计8等份;再取2个面包,每个面包平均切成4等份,合计8等份;剩下的1个面包平均切成8等份。那么,最终每个人能拿到3份面包,如此保证了每个人分得的数量和份量都是一样的。

数学上把项数最少的展式称为最优展式,而兰德纸草书中的展式并不全都是最优展式。对于同一个数字来说,用古埃及分数表达的方式有很多种。比如2/3=1/2+1/6,而其中1/6=1/7+1/42,因此可表达为2/3=1/2+1/7+1/42;其中1/42=1/43+1/1806,因此又可表达为2/3=1/2+1/7+1/43+1/1806。如此分解下去,可以将展式的项数无限扩展。由此可知,古埃及人在当时还没有形成一套科学合理性很完整的数学体系。

描述

古埃及人使用单位分数的和(形如1/a的, a是自然数)表示一切有理数。如: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(0<a<b<1000),编程计算最好的表达方式。

输出

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

样例1

19 45
5 6 18

数据说明

共有10个测试用例,每个10分。对于 100%的数据,0<a<b<1000。

第九届重电程序设计大赛编程正式赛

未参加
状态
已结束
规则
IOI
题目
8
开始于
2022-5-24 13:30
结束于
2022-5-24 17:00
持续时间
3.5 小时
主持人
参赛人数
104