#P3025. [Balkan2003]Farey数列

    ID: 2157 传统题 1000ms 512MiB 尝试: 115 已通过: 36 难度: 7 上传者: 标签>CF2300提高+/省选-二分第 k 小莫比乌斯反演交换求和顺序线性筛一维前缀和有理数精确运算

[Balkan2003]Farey数列

题目描述

把所有分子和分母都小于 n n 的最简真分数从小到大排成一行,形成的序列称为 Farey 序列。

例如:n=4 n=4 时序列是 $\displaystyle \frac {1}{4},\frac {1}{3},\frac {2}{3},\frac {3}{4}$。

求出 n n 所对应的 Farey 序列中第 k k 小的数。

输入格式

给出 n,k n,k ,保证输入合法。

输出格式

输出 p p , q q ,代表你所找到的分数为 pq \displaystyle \frac {p}{q} 。

样例输入

5 6

样例输出

3 5

数据规模与约定

对于 100%100\% 的数据,1<n≤4×104 1<n \leq 4\times 10^4 。