卢俊达

题目大意：

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

思路：

利用两层循环进行枚举分子分母，当分子分母最大公约数为1时记录下来。

代码：

/*
ID: lujunda1
LANG: C++
PROG: frac1
*/
#include<iostream>
#include<stdio.h>
using namespace std;
#define datasize (130+1)*130/2
struct point
//利用结构体对分数的分子分母进行封装。 
{
	int a;
	int b;
}arry[datasize];
int gcd(int y,int x)
//求最大公约数。 
{
	return y%x?gcd(x,y%x):x;
}
int cmp(const void* m,const void* n)
//比较函数，对point类型的分数进行大小比较。 
{
	double a=double((*(point*)m).a)/double((*(point*)m).b);
	double b=double((*(point*)n).a)/double((*(point*)n).b);
	if(a>b)
		return 1;
	if(a==b)
		return 0;
	if(a<b)
		return -1;
}
int main()
{
	freopen("frac1.in","r",stdin);
	freopen("frac1.out","w",stdout);
	int n;
	while(~scanf("%d",&n))
	{
		int total=0;
		//total表示除0/1和1/1外最简分数的数量。 
		for(int i=1;i<=n;i++)
			for(int j=1;j<i;j++)
				if(gcd(i,j)==1)
				//最大公约数等于1时，说明分子分母互质。 
				{
					arry[total].a=j;
					arry[total++].b=i;
				}
		qsort(arry,total,sizeof(arry[0]),cmp);
		//排序 
		printf("0/1\n");
		for(int i=0;i<total;i++)
			printf("%d/%d\n",arry[i].a,arry[i].b);
		printf("1/1\n");
	}
}