Description

Source: BIO 1997 Round 1 Question 3.

In ancient Egypt, people represented any rational number as a sum of unit fractions (fractions of the form $\dfrac{1}{a}$, where $a$ is a positive integer). For example, $\dfrac{2}{3} = \dfrac{1}{2} + \dfrac{1}{6}$, but $\dfrac{2}{3} = \dfrac{1}{3} + \dfrac{1}{3}$ is not allowed because addends must be distinct. For a fraction $\dfrac{a}{b}$ there are many representations, but which one is best? First, fewer terms are better than more terms. Second, among representations with the same number of terms, the larger the smallest unit fraction, the better. For example:

$$\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}$$

The last one is the best because $\dfrac{1}{18}$ is larger than $\dfrac{1}{180}, \dfrac{1}{45}, \dfrac{1}{30}$.

Note that there can be multiple optimal solutions. For example:

$$\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}$$

Since the smallest unit fraction is the same in method one and method two, both are optimal solutions.

Given $a, b$, write a program to compute the best representation. It is guaranteed that an optimal solution satisfies: the smallest unit fraction $\ge \cfrac{1}{10^7}$.

Input Format

A single line with two integers, the values of $a$ and $b$.

Output Format

Output several integers in increasing order, which are the denominators of the unit fractions, in order.

19 45

5 6 18

Hint

$1 \lt a \lt b \lt 1000$.

Translated by ChatGPT 5