#P10396. [2021年联测]分数排序
[2021年联测]分数排序
题目描述
把分母不超过 的所有最简真分数按从小到大排列,求第 个分数。分数 是最简真分数,当且仅当 且 。
输入格式
一行两个正整数 。
输出格式
一行两个正整数 ,表示第 个分数的分子和分母。
样例
6 5
2 5
666 66666
300 607
数据范围
。,其中 是区间 内与 互质的整数个数。
| 子任务 | 特殊限制 | 原赛分值 |
|---|---|---|
| 1 | 20 | |
| 2 | 30 | |
| 3 | 50 |
把分母不超过 n 的所有最简真分数按从小到大排列,求第 k 个分数。分数 p/q 是最简真分数,当且仅当 1≤p<q 且 gcd(p,q)=1。
一行两个正整数 n,k。
一行两个正整数 p,q,表示第 k 个分数的分子和分母。
6 5
2 5
666 66666
300 607
2≤n≤107。1≤k<∑i=1nφ(i),其中 φ(i) 是区间 [1,i] 内与 i 互质的整数个数。
| 子任务 | 特殊限制 | 原赛分值 |
|---|---|---|
| 1 | n≤100 | 20 |
| 2 | n≤1000 | 30 |
| 3 | n≤107 | 50 |