上海市计算机学会竞赛平台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;
}