题目名称 3897. 埃及分数
输入输出 fraction.in/out
难度等级 ★★★☆
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试数据 20
题目来源 Gravatarsyzhaoss 于2023-05-09加入
开放分组 全部用户
提交状态
分类标签
分享题解
通过:0, 提交:0, 通过率:0%
关于 埃及分数 的近10条评论(全部评论)

3897. 埃及分数

★★★☆   输入文件:fraction.in   输出文件:fraction.out   评测插件
时间限制:1 s   内存限制:256 MiB

【题目描述】

在古埃及,人们使用单位分数的和(形如 $\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$ 的值。

【输出格式】

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

【样例 1 输入】

19 45

【样例 1 输出】

5 6 18

【数据范围】

$1 < a < b < 1000$

【来源】

来源:BIO 1997 Round 1 Question 3