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

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

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 0  Solved: 0
Submit Status Web Board

Creator:

Description

来源:BIO 1997 Round 1 Question 3

在古埃及,人们使用单位分数的和(形如 1a\dfrac{1}{a}a1 的,aaa 是自然数)表示一切有理数。如:23=12+16\dfrac{2}{3} = \dfrac{1}{2} + \dfrac{1}{6}32=21+61,但不允许 23=13+13\dfrac{2}{3} = \dfrac{1}{3} + \dfrac{1}{3}32=31+31,因为加数中有相同的。对于一个分数 ab\dfrac{a}{b}ba,表示方法有很多种,但是哪种最好呢?首先,加数少的比加数多的好,其次,加数个数相同的,最小的分数越大越好。如:

1945=13+112+1180\frac{19}{45} = \frac{1}{3} + \frac{1}{12} + \frac{1}{180}4519=31+121+18011945=13+115+145\frac{19}{45} = \frac{1}{3} + \frac{1}{15} + \frac{1}{45}4519=31+151+4511945=13+118+130\frac{19}{45} = \frac{1}{3} + \frac{1}{18} + \frac{1}{30}4519=31+181+3011945=14+16+1180\frac{19}{45} = \frac{1}{4} + \frac{1}{6} + \frac{1}{180}4519=41+61+18011945=15+16+118\frac{19}{45} = \frac{1}{5} + \frac{1}{6} + \frac{1}{18}4519=51+61+181

最好的是最后一种,因为 118\dfrac{1}{18}1811180,145,130,118\dfrac{1}{180}, \dfrac{1}{45}, \dfrac{1}{30}, \dfrac{1}{18}1801,451,301,181 都大。
注意,可能有多个最优解。如:

59211=14+136+1633+13798\frac{59}{211} = \frac{1}{4} + \frac{1}{36} + \frac{1}{633} + \frac{1}{3798}21159=41+361+6331+3798159211=16+19+1633+13798\frac{59}{211} = \frac{1}{6} + \frac{1}{9} + \frac{1}{633} + \frac{1}{3798}21159=61+91+6331+37981

由于方法一与方法二中,最小的分数相同,因此二者均是最优解。

给出 a,ba,ba,b,编程计算最好的表达方式。保证最优解满足:最小的分数 ≥1107\ge \cfrac{1}{10^7}1071


Input

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


Output

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


Sample Input

19 45

Sample Output

5 6 18

HINT

00<a<b<1000


Source/Category


Submit Status