『算法-ACM 竞赛』洛谷 458 顺序的分数 Ordered Fractions（有技巧的枚举）+C++类封装=精简代码

题目描述
输入一个自然数 N,对于一个最简分数 a/b（分子和分母互质的分数）,满足 1<=b<=N,0<=a/b<=1,请找出所有满足条件的分数。

这有一个例子，当 N=5 时，所有解为：

0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1

给定一个自然数 N，1<=n<=160，请编程按分数值递增的顺序输出所有解。

注：①0 和任意自然数的最大公约数就是那个自然数 ② 互质指最大公约数等于 1 的两个自然数。

输入输出格式
输入格式：
单独的一行一个自然数 N(1..160)

输出格式：
每个分数单独占一行，按照大小次序排列

输入输出样例
输入样例#1：
5
输出样例#1：
0/1
1/5
1/4
1/3
2/5
1/2
3/5
2/3
3/4
4/5
1/1
说明
USACO 2.1

翻译来自 NOCOW
没有什么可以说的，直接按照题目给的枚举即可，网上的代码好长，好乱，看到一个小伙计用类写的，启发了我，抛玉引砖，有一点是比较分数大小，交叉相乘。

#include<bits/stdc++.h>
using namespace std;
struct Fract
{
    int n,d;
    bool operator < (const Fract & tmp){return n * tmp.d < tmp.n * d;}
    void print(){  cout << n << '/' << d<<endl;}
    Fract(int a,int b):n(a),d(b){}
};
int main()
{
    int n;
    vector<Fract> res;
    res.push_back(Fract(0, 1));
    cin >> n;
    for (int i = 2; i <= n; i++)
        for (int j = 1; j < i; j++)
            if (__gcd(j, i) == 1)     res.push_back(Fract(j, i ));
    res.push_back(Fract(1, 1 ));
    sort(res.begin(),res.end());
    for (auto i=res.begin();i!=res.end();i++)    i->print();
    return 0;
}