题目描述
KJDH是个十分善于探索的孩子，有一天他把分子分母小于等于n的最简分数列在了纸上，他想找到这些分数里第k小的数，这对于KJDH来说当然是非常轻易，但是KJDH最近多了很多妹子，他还要去找妹子聊天，所以这个任务就交给你了。
输入
输入文件只有一行，两个数n，k，保证输入合法。
输出
输出文件包含两个用空格隔开的数，x，y，表示第k小的分数x/y。
样例输入
5 6 100 200
样例输出
3 5 6 91
提示
n=5时，有这些分数1/2,1/3,2/3,1/4,3/4,1/5,2/5,3/5,4/5。其中第6小的是3/5。
【数据规模与约定】
对于60%的数据，n<=2000
对于100%的数据，n<=50000
题解
这道题刚看到的时候完全没有头绪啊，打了暴力都感觉要T
后来听了正解发现是个比较巧妙的思想
我们首先二分一个小数
然后再找到最接近这个小数的分数——比如说二分出来的mid，你要找最接近的分数，我们可以枚举2~n为分母，这样我们可以直接算出分子了
找到分数后，我们需要计算小于等于这个分数的个数——那么我们同样也可以枚举2~n为分母，同样也可以算出分子，然后就是一个容斥啦
具体可以看一下代码
1 #include<bits/stdc++.h> 2 #define N 50005 3 using namespace std; 4 int n,k,sum; 5 bool flag[N]; 6 vector<int>prime[N]; 7 struct node{ 8 int x,y; 9 }; 10 bool operator < (node x,node y){ 11 return x.x*y.y<x.y*y.x; 12 } 13 void dfs(int now,int s,int num,int limit,int x){ 14 if (now==prime[x].size()){ 15 if (num&1) sum-=limit/s; 16 else sum+=limit/s; 17 return; 18 } 19 dfs(now+1,s,num,limit,x); 20 dfs(now+1,s*prime[x][now],num+1,limit,x); 21 } 22 int calc(int x,int y){ 23 sum=0; 24 dfs(0,1,0,x,y); 25 return sum; 26 }//计算<=x的数中与y的gcd值为1的个数 27 int check(int x,int y){ 28 int ans=0; 29 for (int i=2;i<=n;i++){ 30 int s=i*x/y; 31 ans+=calc(s,i); 32 } 33 return ans; 34 } 35 node find(double x){ 36 node s={0,1}; 37 for (int i=2;i<=n;i++){ 38 int y=(int)(x*i); 39 if (s<(node){y,i}) s=(node){y,i}; 40 } 41 return s; 42 } 43 void pre(){ 44 for (int i=2;i<=n;i++) 45 if (!flag[i]) 46 for (int j=i;j<=n;j+=i) 47 flag[j]=true,prime[j].push_back(i); 48 } 49 int main(){ 50 scanf("%d%d",&n,&k); 51 pre(); 52 double l=0.0,r=1.0;//二分一个小数 53 while (true){ 54 double mid=(l+r)/2.0; 55 node s=find(mid);//查找离这个小数最接近的分数 56 int num=check(s.x,s.y);//记录小于等于s的分数的个数 57 if (num<k) l=mid; else 58 if (num>k) r=mid; else{ 59 printf("%d %d ",s.x,s.y); 60 return 0; 61 } 62 } 63 return 0; 64 }