分数排序

题目描述

给定正整数 $n$ 与 $k$，将分母范围在 $1$ 到 $n$ 之间的所有最简真分数排序，请输出其中第 $k$ 小的分数。

如，$n=4$ 时，分母范围在 $1$ 到 $4$ 之间的最简真分数有

$$\frac{1}{2}, \frac{1}{3}, \frac{2}{3}, \frac{1}{4}, \frac{3}{4}$$

排序后有

$$\frac{1}{4} < \frac{1}{3} < \frac{1}{2} < \frac{2}{3} < \frac{3}{4}$$

其中第二项为 $1/3$，第四项为 $2/3$。

输入格式

两个整数 $n$ 与 $k$，保证 $k$ 是一个合理的参数，即保证分母不超过 $n$ 的最简真分数至少有 $k$ 个。

输出格式

一个分数，形如 A/B，A 与 B 分别表示分子及分母，它们应该是既约互素的。

数据范围

对于 30% 的数据，$n \le 100$； 对于 60% 的数据，$n \le 1000$； 对于 100% 的数据，$1 < n \le 50000$，$1 \le k \le 200000$。

样例输入

4 3

样例输出

1/2

知识点与难度

本题涉及的知识点从属于 GESP五级（二分答案、数论），难度等级：⭐⭐⭐⭐。

---

测试点分布

Subtask	分值	测试点编号	说明
0	10	1~2	样例
1	20	3~8	小规模
2	15	9~11	Hack
3	30	12~20	中大规模
4	25	21~25	随机回归