题目描述

给定正整数 n 与 k，

将分母范围在 1 到 n 之间的所有最简真分数排序，

请输出其中第 k 小的分数。

输入格式

两个整数 n 与 k，

保证 k 是一个合理的参数，

即保证分母不超过 n 的最简真分数至少有 k 个。

输出格式

一个分数，形如 A/B， A 与 B 分别表示分子及分母，它们应该是既约互素的。

数据范围

• 对于 30%30% 的数据，𝑛≤100n≤100；
• 对于 60%60% 的数据，𝑛≤1000n≤1000；
• 对于 100%100% 的数据，1<𝑛≤500001<n≤50000，1≤𝑘≤2000001≤k≤200000。

样例数据

4 3

1/2

#include <bits/stdc++.h>
using namespace std;
struct node{
	int fenzi;
	int fenmu;
	double num;
}a[1000];
double cmp(node x,node y){
	return x.num<y.num;
}bool gcd(int n1,int n2){//可以直接用__gcd()
	int i;
	for(i=2;i<=n1;i++){
		if(n1%i=&