AcWing 1360. 有序分数
原题链接
简单
作者:
叙利亚悍匪_0
,
2024-03-30 16:09:15
,
所有人可见
,
阅读 1
结构体
#include<iostream>
#include<algorithm>
using namespace std;
int n;
double stau[1000010];
struct Point
{
double st;
double up;
double down;
}point[1000010];
int gcd(int a,int b)
{
if(b == 0) return a;
else return gcd(b,a%b);
}
bool cmp(struct Point x, struct Point y)
{
return x.st < y.st;
}
int main()
{
cin>>n;
int cnt = 0;
//枚举分母
for(int i = 2;i<=n;i++)
{
//枚举分子
for(int j = 1;j<i;j++)
{
//最简
if(gcd(i,j) == 1)
{
double ti = i,tj = j;
point[cnt].st = tj / ti;
point[cnt].up = tj;
point[cnt].down = ti;
cnt++;
}
if(gcd(i,j) != 1)
{
double ti = i,tj = j;
ti = ti / gcd(i,j);
tj = tj / gcd(i,j);
point[cnt].up = tj;
point[cnt].down = ti;
point[cnt].st = tj / ti;
cnt++;
}
}
}
sort(point,point+cnt,cmp);
cout<<"0/1"<<endl;
for(int i = 0;i<cnt;i++)
{
if(point[i].st == point[i+1].st) continue;
cout<<point[i].up<<"/"<<point[i].down<<endl;
}
cout<<"1/1"<<endl;
}