5648 - 提高:迭代加深搜索:埃及分数

在古埃及,人们使用单位分数的和(形如 \dfrac{1}{a} 的,a 是自然数)表示一切有理数。如:\dfrac{2}{3} = \dfrac{1}{2} + \dfrac{1}{6},但不允许 \dfrac{2}{3} = \dfrac{1}{3} + \dfrac{1}{3},因为加数中有相同的。对于一个分数 \dfrac{a}{b},表示方法有很多种,但是哪种最好呢?首先,加数少的比加数多的好,其次,加数个数相同的,最小的分数越大越好。如: \begin{aligned} \frac{19}{45} &= \frac{1}{3} + \frac{1}{12} + \frac{1}{180}\ \frac{19}{45} &= \frac{1}{3} + \frac{1}{15} + \frac{1}{45}\ \frac{19}{45} &= \frac{1}{3} + \frac{1}{18} + \frac{1}{30}\ \frac{19}{45} &= \frac{1}{4} + \frac{1}{6} + \frac{1}{180}\ \frac{19}{45} &= \frac{1}{5} + \frac{1}{6} + \frac{1}{18}\ \end{aligned} 最好的是最后一种,因为 \dfrac{1}{18}\dfrac{1}{180}, \dfrac{1}{45}, \dfrac{1}{30} 都大。
注意,可能有多个最优解。如: \begin{aligned} \frac{59}{211} &= \frac{1}{4} + \frac{1}{36} + \frac{1}{633} + \frac{1}{3798}\ \frac{59}{211} &= \frac{1}{6} + \frac{1}{9} + \frac{1}{633} + \frac{1}{3798}\ \end{aligned} 由于方法一与方法二中,最小的分数相同,因此二者均是最优解。

给出 a,b,编程计算最好的表达方式。保证最优解满足:最小的分数>=10^7

输入

一行两个整数,分别为 ab 的值。

输出

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

样例

输入

19 45

输出

5 6 18

提示

1 \lt a \lt b \lt 1000

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题