A70801 | 分数
来源编程题
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
上完物理实验课,紧接着就上数学课,课上大名鼎鼎的 Z 老师按照惯例先给大家讲一 个故事,今天的第一堂课当然是讲他的得意弟子青年数学家恽之玮勇夺国际数学奥林匹克(International Mathematical Olympiad,简称 IMO)金牌的故事,故事讲完后,Z 老师组织大家讨论了一道当年恽之玮学长遇到的难题,问题并不复杂:给你一个最简真分数, 找出另一个分子分母都在 1 到 32767 之间的最简真分数,使它与给定的分数最为接近,这 里最为接近指的是两数之间的差最小,如 5/6 就比 3/4 更接近 4/5,因为 5/6 与 4/5 相差 不到 0.4,而 3/4 与 4/5 相差了 0.5。所谓最简真分数也就是说分子和分母的最大公约数为 1,并且分子小于分母。
输入格式
输入数据仅有一行包含两个用空格隔开的正整数 N 和 D,其中 1≤N<D≤32767,分别 是给你的分数的分子和分母。
输出格式
输出数据仅有一行包含两个正整数,分别是你求出的最接近的真分数的分子和分母, 并且分子分母都在 1 到 32767 之间。如果满足条件的真分数不止一个,输出其中数值最小的那个。输出时两数之间严格用一个空格隔开,行末没有多余的空格。
输入输出样例
输入 #1
2 3
输出 #1
21845 32767
思路
用辗转相除:反复用较大数对较小数取余,直到余数为 0。
步骤
1. 读入两个正整数。
2. 用欧几里得算法求 GCD。
3. 输出结果。
C++ 编辑器
输入
输出
可保存默认模板;新题优先使用已保存模板。
当前快捷键仅展示,暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好,我是作答助手。可以问思路、复杂度、样例含义或代码报错原因;不会直接给出完整 AC 代码。
确定要清空代码吗?