/ WHOJ / 题库 /

埃及分数

埃及分数

题目背景

来源:BIO 1997 Round 1 Question 3

题目描述

在古埃及,人们使用单位分数的和(形如 \(\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}\),表示方法有很多种,但是哪种最好呢?首先,加数少的比加数多的好,其次,加数个数相同的,最小的分数越大越好。如:
\(\dfrac{19}{45} \&= \dfrac{1}{3} + \dfrac{1}{12} + \dfrac{1}{180}\)

\(\dfrac{19}{45} \&= \dfrac{1}{3} + \dfrac{1}{15} + \dfrac{1}{45}\)

\(\dfrac{19}{45} \&= \dfrac{1}{3} + \dfrac{1}{18} + \dfrac{1}{30}\)

\(\dfrac{19}{45} \&= \dfrac{1}{4} + \dfrac{1}{6} + \dfrac{1}{180}\)

\(\dfrac{19}{45} \&= \dfrac{1}{5} + \dfrac{1}{6} + \dfrac{1}{18}\)

最好的是最后一种,因为 \(\dfrac{1}{18}\) 比 \(\dfrac{1}{180}, \dfrac{1}{45}, \dfrac{1}{30}\) 都大。

注意,可能有多个最优解。如:

\(\dfrac{59}{211} \&= \dfrac{1}{4} + \dfrac{1}{36} + \dfrac{1}{633} + \dfrac{1}{3798}\)

\(\dfrac{59}{211} \&= \dfrac{1}{6} + \dfrac{1}{9} + \dfrac{1}{633} + \dfrac{1}{3798}\)

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

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

格式

输入格式

一行两个整数,分别为 \(a\) 和 \(b\) 的值。

输出格式

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

样例1

样例输入1

19 45

样例输出1

5 6 18

限制

\(1 \lt a \lt b \lt 1000\)