题目描述

将分母不超过 $n$ 的所有最简真分数从小到大排成一行，求第 $k$ 个位置上的分数

一个分数 $\frac{p}{q}$ 为最简真分数，当且仅当 $1\leq p < q$ 且 $p,q$ 互质

输入格式

一行两个正整数 $n, k$，用空格分隔

输出格式

一行两个正整数 $p, q$，用空格分隔，代表答案为 $\frac{p}{q}$

样例输入 1

6 5

样例输出 1

2 5

样例输入 2

666 66666

样例输出 2

300 607

数据范围与约定

对于$24\%$的数据： $n \leq 10$

对于$60\%$的数据： $n \leq 100$

对于$97\%$的数据： $n \leq 1000$

对于$100\%$的数据： $2\leq n \leq 10^7$，$1 \leq k < \sum_{i=1}^n \varphi (i)$，其中 $\varphi(n)$ 代表比 $n$ 小的数中与 $n$ 互质的数的个数

时间限制：$1\texttt{s}$

空间限制：$256\texttt{MB}$