2465: 分数

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:23 Solved:17

Description

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

Input

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

Output

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

Sample Input Copy

2 3

Sample Output Copy

21845 32767

HINT

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

Source/Category