测评会员优惠活动进行中 · 开通 VIP,有效期内测评不限次 VIP 优惠中 · 测评不限次 立即查看

A70801. 分数

编程题 基础

题目描述

上完物理实验课,紧接着就上数学课,课上大名鼎鼎的 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. 输出结果。