#E. 「一本通 1.3 练习 1」埃及分数

    Type: Default 1000ms 512MiB

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

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

来源:BIO 1997 Round 1 Question 3

在古埃及,人们使用单位分数的和(形如 1a\dfrac{1}{a} 的,aa 是自然数)表示一切有理数。如:23=12+16\dfrac{2}{3} = \dfrac{1}{2} + \dfrac{1}{6},但不允许 23=13+13\dfrac{2}{3} = \dfrac{1}{3} + \dfrac{1}{3},因为加数中有相同的。对于一个分数 ab\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} $$

最好的是最后一种,因为 118\dfrac{1}{18} 比 $\dfrac{1}{180}, \dfrac{1}{45}, \dfrac{1}{30}, \dfrac{1}{18}$ 都大。
注意,可能有多个最优解。如:

$$\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,ba,b,编程计算最好的表达方式。保证最优解满足:最小的分数 1107\ge \cfrac{1}{10^7}

输入格式

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

输出格式

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

样例

19 45
5 6 18

数据范围与提示

0<a<b<10000 \lt a \lt b \lt 1000

初一竞赛组——DFS剪枝

Not Claimed
Status
Done
Problem
7
Open Since
2024-10-8 15:00
Deadline
2024-11-9 23:59
Extension
24 hour(s)