AcWing 1360. 有序分数
原题链接
简单
作者:
Ronnie123
,
2024-04-06 17:14:09
,
所有人可见
,
阅读 3
#include<bits/stdc++.h>
using namespace std;
const int N=200;
typedef pair<int,int>PII;
#define x first
#define y second
PII q[N*N];
int cnt;
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
bool cmp(PII a,PII b)
{
return a.x*b.y<a.y*b.x;
}
int main()
{
int n;
cin>>n;
for(int i=0;i<=n;i++)
{
for(int j=0;j<=i;j++)
{
if(gcd(i,j)==1)
{
q[cnt++]={j,i};
}
}
}
sort(q,q+cnt,cmp);
for(int i=0;i<cnt;i++)
{
printf("%d/%d\n",q[i].x,q[i].y);
}
return 0;
}