输入一个自然数N，我们总可以得到一些满足“1≤b≤N,0≤a/b≤1”条件的最简分数a/b（分子和分母互质的分数），请找出所有满足条件的分数。
比方说，当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
输出为一个列表，每个分数单独占一行，按照实际大小从小到大排列
样例输入
5
样例输出
0/1
1/5
1/4
1/3
2/5
1/2
3/5
2/3
3/4
4/5
1/1
#include<stdio.h>
#include<algorithm>
using namespace std;
int mgy(int a, int b)//求最大公约数
{
if(b==0) return a;
else return mgy(b, a%b);
}
struct out {
int v[2];
float value;
bool operator < (const out &b) const{
return value<b.value;
}
}buf[25600];
int main()
{
int n;
scanf("%d",&n);
int i=0;
for(int b=1;b<=n;b++){
for(int a=0;a<=b;a++){
if(mgy(a,b)==1){
buf[i].v[0]=a;
buf[i].v[1]=b;
buf[i].value=float(a)/b;
i++;
}
}
}
sort(buf,buf+i);
for(int j=0;j<i;j++) printf("%d/%d\n",buf[j].v[0],buf[j].v[1]);
return 0;
}
思想：用b遍历0~N的所有数，用a遍历1~b的所有数，留下a/b是最简的分数，再对这些分数排序，最终按从小到大输出。其中，留下最简分数，需要求a，b的最大公约数，最大公约数为1的分数就是最简分数。排序用C++库中的sort函数即可。
