#4301. 「一本通 1.3 练习 1」埃及分数

「一本通 1.3 练习 1」埃及分数

[{"sectionTitle":"题目描述","type":"Text","text":"来源:BIO 1997 Round 1 Question 3\r\n\r\n在古埃及,人们使用单位分数的和(形如 dfrac1a\\dfrac{1}{a} 的,aa 是自然数)表示一切有理数。如:dfrac23=dfrac12+dfrac16\\dfrac{2}{3} = \\dfrac{1}{2} + \\dfrac{1}{6},但不允许 dfrac23=dfrac13+dfrac13\\dfrac{2}{3} = \\dfrac{1}{3} + \\dfrac{1}{3},因为加数中有相同的。对于一个分数 dfracab\\dfrac{a}{b},表示方法有很多种,但是哪种最好呢?首先,加数少的比加数多的好,其次,加数个数相同的,最小的分数越大越好。如:\r\n$$\r\n\begin{aligned}\r\n\frac{19}{45} &= \frac{1}{3} + \frac{1}{12} + \frac{1}{180}\\\r\n\frac{19}{45} &= \frac{1}{3} + \frac{1}{15} + \frac{1}{45}\\\r\n\frac{19}{45} &= \frac{1}{3} + \frac{1}{18} + \frac{1}{30}\\\r\n\frac{19}{45} &= \frac{1}{4} + \frac{1}{6} + \frac{1}{180}\\\r\n\frac{19}{45} &= \frac{1}{5} + \frac{1}{6} + \frac{1}{18}\\\r\n\end{aligned}\r\n$$\r\n最好的是最后一种,因为 dfrac118\\dfrac{1}{18} 比 $\\dfrac{1}{180}, \\dfrac{1}{45}, \\dfrac{1}{30}, \\dfrac{1}{18}$ 都大。 \r\n注意,可能有多个最优解。如:\r\n$$\r\n\begin{aligned}\r\n\frac{59}{211} &= \frac{1}{4} + \frac{1}{36} + \frac{1}{633} + \frac{1}{3798}\\\r\n\frac{59}{211} &= \frac{1}{6} + \frac{1}{9} + \frac{1}{633} + \frac{1}{3798}\\\r\n\end{aligned}\r\n$$\r\n由于方法一与方法二中,最小的分数相同,因此二者均是最优解。\r\n\r\n给出 a,ba,b,编程计算最好的表达方式。保证最优解满足:最小的分数 gecfrac1107\\ge \\cfrac{1}{10^7}。 \r\n","subType":"markdown"},{"sectionTitle":"输入格式","type":"Text","text":"一行两个整数,分别为 aabb 的值。","subType":"markdown"},{"sectionTitle":"输出格式","type":"Text","text":"输出若干个数,自小到大排列,依次是单位分数的分母。","subType":"markdown"},{"sectionTitle":"样例","type":"Sample","text":"","subType":"markdown","payload":["19 45","5 6 18"]},{"sectionTitle":"数据范围与提示","type":"Text","text":"0ltaltblt10000 \\lt a \\lt b \\lt 1000","subType":"markdown"}]