#P10396. [2021年联测]分数排序

    ID: 9513 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 9 上传者: 标签>CF2700省选/NOI-莫比乌斯反演线性筛一维前缀和整除分块类欧几里得算法Stern–Brocot 树倍增寻找边界二分查找

[2021年联测]分数排序

题目描述

把分母不超过 nn 的所有最简真分数按从小到大排列,求第 kk 个分数。分数 p/qp/q 是最简真分数,当且仅当 1≤p<q1\le p<q 且 gcd⁡(p,q)=1\gcd(p,q)=1。

输入格式

一行两个正整数 n,kn,k。

输出格式

一行两个正整数 p,qp,q,表示第 kk 个分数的分子和分母。

样例

6 5
2 5
666 66666
300 607

数据范围

2≤n≤1072\le n\le10^7。1≤k<∑i=1nφ(i)1\le k<\sum_{i=1}^n\varphi(i),其中 φ(i)\varphi(i) 是区间 [1,i][1,i] 内与 ii 互质的整数个数。

子任务 特殊限制 原赛分值
1 n≤100n\le100 20
2 n≤1000n\le1000 30
3 n≤107n\le10^7 50

原 PDF 题面