分数排序 内存限制: 256 Mb时间限制: 1000 ms

本文主要是介绍分数排序 内存限制: 256 Mb时间限制: 1000 ms，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

给定正整数 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==0&&n2%i==0)return false;}return true;
}int main(){int t,n,i,j,count=0;cin>>n>>t;for(i=1;i<=n;i++){for(j=1;j<i;j++){if(gcd(j,i)){a[count].fenzi=j,a[count].fenmu=i;a[count].num=a[count].fenzi*1.0/a[count].fenmu*1.0;count++;}}}sort(a,a+count,cmp);cout<<a[t-1].fenzi<<"/"<<a[t-1].fenmu;
}

 

这篇关于分数排序 内存限制: 256 Mb时间限制: 1000 ms的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---