| 题目名称 | 3897. 埃及分数 |
|---|---|
| 输入输出 | fraction.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 20 |
| 题目来源 |
|
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过:0, 提交:0, 通过率:0% | |||
| 关于 埃及分数 的近10条评论(全部评论) |
|---|
在古埃及,人们使用单位分数的和(形如 $\frac{1}{a}$ 的,$a$ 是正整数)表示一切有理数。如:$\frac{2}{3} = \frac{1}{2} + \frac{1}{6}$,但不允许 $\frac{2}{3} = \frac{1}{3} + \frac{1}{3}$,因为加数中有相同的。对于一个分数 $\frac{a}{b}$,表示方法有很多种,但是哪种最好呢?首先,加数少的比加数多的好,其次,加数个数相同的,最小的分数越大越好。如:
$$\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}$$
最好的是最后一种,因为 $\frac{1}{18}$ 比 $\frac{1}{180}, \frac{1}{45}, \frac{1}{30}$ 都大。
注意,可能有多个最优解。如:
$$\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}$$
由于方法一与方法二中,最小的分数相同,因此二者均是最优解。
给出 $a,b$,编程计算最好的表达方式。保证最优解满足:最小的分数 $\ge \frac{1}{10^7}$。
一行两个整数,分别为 $a$ 和 $b$ 的值。
输出若干个数,自小到大排列,依次是单位分数的分母。
19 45
5 6 18
$1 < a < b < 1000$
来源:BIO 1997 Round 1 Question 3