洛谷1458 顺序的分数

本题地址： http://www.luogu.org/problem/show?pid=1458

题目描述

输入一个自然数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：

输出样例#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

【思路】

gcd+排序

【代码】

 1 #include<iostream>
 2 #include<vector>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 int n;
 7 struct Node{
 8     int x,y;
 9     bool operator < (const Node& rhs) const{
10        return x*rhs.y < y*rhs.x;
11     }
12 };
13 vector<Node> ans;
14 
15 inline int gcd(int a,int b) {
16     if(!b) return a;
17     return gcd(b,a%b);
18 }
19 
20 int main() {
21     cin>>n;
22     int g;
23     for(int i=1;i<=n;i++)  for(int j=1;j<i;j++){
24         g=gcd(j,i);
25         if(g!=1) continue;
26         ans.push_back((Node){j,i});
27     }
28     sort(ans.begin(),ans.end());
29     cout<<"0/1
";
30     for(int i=0;i<ans.size();i++) cout<<ans[i].x<<"/"<<ans[i].y<<"
";
31     cout<<"1/1";
32     return 0;
33 }