1223: Max Fraction

题目描述

三个数据结构班级A,B,C进行了期末考，助教小明被老师要求找出三个班级分数第二高的同学。于是小明先找出A班最高分，B班最高分，C班最高分，再比较得到三个班最高分。然后小明去掉了最高分，用最高分所在班级次高分替代，重复上述过程。终于他成功找到了三个班级期末考试亚军是小红。说巧不巧，这时小红找到了助教小明，向他请教了一个问题，具体如下

定义分数集合 $S_N={ p/q | p,q \in N^+, 1 <= p < q <= N, gcd(p,q) = 1}$, gcd表示最大公因数. 例如 $S_4={1/2,1/3,2/3,1/4,3/4}$. 问集合 $S_N$ 中第 $K$ 大的数为多少 ?

小明一脸懵逼并希望求助于你。请你帮帮小明。

Tips: 集合 $S_N$是在二维空间上建立的，我们很难在二维空间上直接找到顺序规律。但是如果我们把它拆成若干个一维的序列，例如把所有分母相同的数抽成一个序列，那么这个序列的顺序是显然的，即随着分子的增大而单调递增。于是我们可以将$S_N$拆解成若干个单调有序的序列，想一想如何合并这些序列？

输入格式

第一行: 两个数分别为 $N,K$

输出格式

输出集合 $S_N$ 中第 $K$ 大的数
依次输出分子分母中间用 / 隔开

样例输入

Sample Input 1

4 2

Sample Input 2

5 5

样例输出

Sample Output 1

2/3

Sample Output 2

1/2

数据范围

输入保证合法 $|S_N| > K$

对于 70% 的数据
$1 <= N,K <= 10^3$

对于 100% 的数据
$1 <= N <= 10^5, 1 <= K <= 5*10^5$

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！