本文迁移自老博客，原始链接为 https://seven.blog.ustc.edu.cn/usacofrac1/
给一个数5，打印出 0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1 求给一个160以内的数，打印出上述形式的序列。 解法：直接排序。先将所有的分数枚举出，去掉没有约分的，然后排序。比较两个分数时，不用算出小数，a的分子乘以b的分母如果小于a的分母乘以b的分子，则a小于b.
#include<iostream>
#include<algorithm>
#include<fstream>
struct point
{
int x;
int y;
};
point cnt[10000];
using namespace std;
bool cmp(point a , point b)
{
return a.x * b.y < a.y * b.x;
}
int gcd(int m , int n)
{
return n == 0 ? m : gcd(n,m%n);
}
int main()
{
ofstream fout ("frac1.out");
ifstream fin ("frac1.in");
int m;
int t = 0;
cnt[t].x = 0;
cnt[t++].y = 1;
fin>>m;
for(int i = 1; i <= m ;i++)
{
cnt[t].x = 1;
cnt[t++].y = i;
}
for(int i = 2 ; i < m ;i++)
for(int j = i + 1 ; j <= m ;j++)
{
if(j % i != 0 && gcd(i , j) == 1)
{
cnt[t].x = i;
cnt[t++].y = j;
}
}
sort(cnt , cnt + t, cmp);
for(int i = 0 ; i < t ;i++)
fout<<cnt[i].x<<"/"<<cnt[i].y<<endl;
return 0;
}
