2009: 【基础】分数

上完物理实验课，紧接着就上数学课，课上大名鼎鼎的 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 之间。如果满足条件的真分数不止一个，输出其中数值最小 的那个。输出时两数之间严格用一个空格隔开，行末没有多余的空格。

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

来源

2014年常州市赛