分数排序 - 問題

#902. 分数排序

統計

This problem is prepared by Suika_predator .

题目描述

将分母不超过 $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}$

About Issues

We understand that our problem archive is not perfect. If you find any issues with the problem, including the statement, scoring configuration, time/memory limits, test cases, etc.

You may use this form to submit an issue regarding the problem. A problem moderator will review your issue and proceed it properly.

STOP! Before you submit an issue, please READ the following guidelines:

This is not a place to publish a discussion, editorial, or requests to debug your code. Your issue will only be visible by you and problem moderators. Other users will not be able to view or reply your issues.
Do not submit duplicated issues. If you have already submitted one, please wait for an moderator to review it. Submitting multiple issues will not speed up the review process and might cause your account to be banned.
Issues must be filed in English or Chinese only.
Be sure your issue is related to this problem. If you need to submit an issue regarding another problem, contest, category, etc., you should submit it to the corresponding page.

Active Issues 0

No issues in this category.

Closed/Resolved Issues 0