1064: 分数

内存限制:128 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:61 通过:15

题目描述

上完物理实验课,紧接着就上数学课,课上大名鼎鼎的Z老师按照惯例先给大家讲一个故事,今天的第一堂课当然是讲他的得意弟子青年数学家恽之玮勇夺国际数学奥林匹克(International Mathematical Olympiad,简称IMO)金牌的故事,故事讲完后,Z老师组织大家讨论了一道当年恽之玮学长遇到的难题,问题并不复杂:给你一个最简真分数,找出另一个分子分母都在132767之间的最简真分数,使它与给定的分数最为接近,这里最为接近指的是两数之间的差最小,如5/6就比3/4更接近4/5,因为5/64/5相差不到0.4,而3/44/5相差了0.5。所谓最简真分数也就是说分子和分母的最大公约数为1,并且分子小于分母。

输入格式

输入数据仅有一行包含两个用空格隔开的正整数ND,其中1≤ND≤32767,分别是给你的分数的分子和分母。

输出格式

输出数据仅有一行包含两个正整数,分别是你求出的最接近的真分数的分子和分母,并且分子分母都在132767之间。如果满足条件的真分数不止一个,输出其中数值最小的那个。输出时两数之间严格用一个空格隔开,行末没有多余的空格。

输入样例 复制

2 3

输出样例 复制

21845 32767

数据范围与提示

样例解释
21845/32767=0.666676839503... ≈0.666666...  = 2/3。
数据范围
30%的数据满足:1≤N<D≤10
60%的数据满足:1≤N<D≤1000
100%的数据满足:1≤N<D≤32767