#P1763. Optimal Egyptian Fraction Representation
Optimal Egyptian Fraction Representation
Optimal Egyptian Fraction Representation
In ancient Egypt, all fractions were written as sums of distinct unit fractions, i.e. fractions of the form (\frac{1}{a}) with (a\in \mathbb{N}). For example, (\frac{2}{3}) can be written as (\frac{1}{2}+\frac{1}{6}) (note that representations like (\frac{1}{3}+\frac{1}{3}) are not allowed since the unit fractions must be distinct). Given a fraction (\frac{a}{b}), there are many possible representations. We define a representation as "better" if it satisfies the following criteria:
- It uses the fewest possible terms.
- Among representations with the same number of terms, the representation whose smallest unit fraction (i.e. the one with the largest denominator) is the largest is better. In other words, if we write (\frac{a}{b} = \frac{1}{x_1}+\frac{1}{x_2}+\cdots+\frac{1}{x_n}) with (x_1 < x_2 < \cdots < x_n), then for two valid representations with the same number of terms, the one with a smaller (x_n) is considered better.
It is guaranteed that the optimal representation always has its smallest term (\ge \frac{1}{10^7}).
For example, one may represent (\frac{19}{45}) in several ways:
[ \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 best representation is the last one because (\frac{1}{18}) is larger than (\frac{1}{180}), (\frac{1}{45}), and (\frac{1}{30}). Note that there can be more than one optimal representation if the smallest term is equal. Your task is, given two positive integers (a) and (b), to compute the best Egyptian fraction representation of (\frac{a}{b}) according to the rules above.
inputFormat
The input consists of two positive integers (a) and (b) (with (a < b)) separated by space, representing the fraction (\frac{a}{b}).
outputFormat
Output the optimal representation in the format:
a/b = 1/x1 + 1/x2 + ... + 1/xn
where the unit fractions are listed in increasing order of their denominators.
sample
2 3
2/3 = 1/2 + 1/6