「一本通 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
在古埃及,人们使用单位分数的和(形如 的, 是自然数)表示一切有理数。如:,但不允许 ,因为加数中有相同的。对于一个分数 ,表示方法有很多种,但是哪种最好呢?首先,加数少的比加数多的好,其次,加数个数相同的,最小的分数越大越好。如:
$$\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} $$最好的是最后一种,因为 比 $\dfrac{1}{180}, \dfrac{1}{45}, \dfrac{1}{30}, \dfrac{1}{18}$ 都大。
注意,可能有多个最优解。如:
由于方法一与方法二中,最小的分数相同,因此二者均是最优解。
给出 ,编程计算最好的表达方式。保证最优解满足:最小的分数 。
输入格式
一行两个整数,分别为 和 的值。
输出格式
输出若干个数,自小到大排列,依次是单位分数的分母。
样例
19 45
5 6 18
数据范围与提示
初一竞赛组——DFS剪枝
- Status
- Done
- Problem
- 7
- Open Since
- 2024-10-8 15:00
- Deadline
- 2024-11-9 23:59
- Extension
- 24 hour(s)