A5563 | 「一本通 1.3 练习 1」埃及分数
时间限制1s
内存限制512MB
通过 / 提交0/0
题目描述
**来源:BIO 1997 Round 1 [Question 3](http://www.olympiad.org.uk/papers/1997/bio/bio97r1q3.html)**
在古埃及,人们使用单位分数的和(形如 $\dfrac{1}{a}$ 的,$a$ 是自然数)表示一切有理数。如:$\dfrac{2}{3} = \dfrac{1}{2} + \dfrac{1}{6}$,但不允许 $\dfrac{2}{3} = \dfrac{1}{3} + \dfrac{1}{3}$,因为加数中有相同的。对于一个分数 $\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} $$
最好的是最后一种,因为 $\dfrac{1}{18}$ 比 $\dfrac{1}{180}, \dfrac{1}{45}, \dfrac{1}{30}$ 都大。
注意,可能有多个最优解。如:
$$ \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,b$,编程计算最好的表达方式。保证最优解满足:最小的分数 $\ge \cfrac{1}{10^7}$。
在古埃及,人们使用单位分数的和(形如 $\dfrac{1}{a}$ 的,$a$ 是自然数)表示一切有理数。如:$\dfrac{2}{3} = \dfrac{1}{2} + \dfrac{1}{6}$,但不允许 $\dfrac{2}{3} = \dfrac{1}{3} + \dfrac{1}{3}$,因为加数中有相同的。对于一个分数 $\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} $$
最好的是最后一种,因为 $\dfrac{1}{18}$ 比 $\dfrac{1}{180}, \dfrac{1}{45}, \dfrac{1}{30}$ 都大。
注意,可能有多个最优解。如:
$$ \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,b$,编程计算最好的表达方式。保证最优解满足:最小的分数 $\ge \cfrac{1}{10^7}$。
输入格式
一行两个整数,分别为 $a$ 和 $b$ 的值。
输出格式
输出若干个数,自小到大排列,依次是单位分数的分母。
输入输出样例
输入 #1
19 45
输出 #1
5 6 18
$0 \lt a \lt b \lt 1000$
C++ 编辑器
输入
输出
可保存默认模板;新题优先使用已保存模板。
当前快捷键仅展示,暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好,我是作答助手。可以问思路、复杂度、样例含义或代码报错原因;不会直接给出完整 AC 代码。
确定要清空代码吗?