题目描述

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
      
        2 #define N 50005 3 using namespace std; 4 int n,k,sum; 5 bool flag[N]; 6 vector
       
        prime[N]; 7 struct node{ 8     int x,y; 9 };10 bool operator < (node x,node y){11     return x.x*y.y
        
         k) r=mid; else{59             printf("%d %d\n",s.x,s.y);60             return 0;61         }62     }63     return 0;64 }