上海市计算机学会竞赛平台2024年4月月赛丙组排序分数
排序分数
内存限制: 256 Mb时间限制: 1000 ms
题目描述
给定正整数 nn，请按从小到大的顺序输出所有大于00 且小于 11 的，分母不超过 nn 的最简分数，例如 n=5n=5 时，输出：
15, 14, 13, 25, 12, 35, 23, 34, 4551, 41, 31, 52, 21, 53, 32, 43, 54
输入格式
- 单个整数表示 nn
输出格式
- 若干行：每行一个分数表示答案。
数据范围
- 30%30% 的数据，2≤n≤102≤n≤10
- 60%60% 的数据，2≤n≤502≤n≤50
- 100%100% 的数据，2≤n≤5002≤n≤500
样例数据
输入:
4
输出:
1/4
1/3
1/2
2/3
3/4
题解：
#include<bits/stdc++.h>
using namespace std;
struct sb{
int f,fe;
double fs;
}a[1300000];
bool cmp(sb a,sb b){
return a.fs<b.fs;
}
int gcd(int x,int y){
int r=y%x;
while(r){
y=x;
x=r;
r=y%x;
}
return x;
}
int main(){
int n,t=0;
cin>>n;
for(int i=2;i<=n;i++){
for(int j=1;j<i;j++){
if(gcd(i,j)==1){
a[t].fs=j*1.0/i;
a[t].f=j;
a[t].fe=i;
t++;
}
}
}
sort(a,a+t,cmp);
for(int i=0;i<t;i++){
cout<<a[i].f<<"/"<<a[i].fe<<endl;
}
return 0;
}