【不可约分数】

题目描述

给出 K 和 N,请你求出第 K 小的不可约分数 p/q ,其中 0<p<q≤N 。

输入格式

输入文件第一行,是一个整数 T(T≤10),表示有 T 组测试数据。
从第二行开始,每行对应一组测试数据。
对于每组测试数据,有两个正整数 N 和 K(1≤K≤N≤100000),用一个空格隔开。

输出格式

对每组数据输出一行,即第 K 小的不可约分数 p/q 。

样例数据 1

输入

4
5 1
5 2
5 3
5 4

输出

1/5
1/4
1/3
2/5

嘛……总之就是一个Stern-Brocot树(不懂请见【Farely序列与Stern-Brocot树】)的问题,已经把70分和100分代码整合上去了,其实100分就是强行把70分的代码改成非递归避免爆栈……

70分:

100分:

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*