题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
int n;
PII a[1000010];
int gcd(int a,int b)
{
if(!b) return a;
return gcd(b,a%b);
}
bool cmp(PII x,PII y)
{
return (double)x.first/(double)x.second < (double)y.first/(double)y.second;
}
int main()
{
cin>>n;
int cnt=0;
a[0]={0,1};
for(int i=1;i<=n;i++)//分母
{
for(int j=1;j<=i;j++)//分子
{
if(gcd(j,i)==1) a[++cnt]={j,i};
}
}
sort(a,a+cnt+1,cmp);
for(int i=0;i<=cnt;i++)
{
printf("%d/%d\n",a[i].first,a[i].second);
}
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla