记录编号	40691	评测结果	AAAAAAAAAAA
题目名称	法雷序列	最终得分	100
用户昵称	hello！	是否通过	通过
代码语言	C++	运行时间	0.043 s
提交时间	2012-07-18 16:36:06	内存使用	25.49 MiB

/*
ID: fuyangh1
PROG: frac1
LANG: C++
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>

using namespace std;
struct num{
	int aa;
	int bb;//分数表示为a/b.
	double size;
}ku[1650000];//1650000
int n;

bool check(int a,int b);
int gcd(int a,int b);

int cmp(const void *a,const void *b)
{
	struct num *c=(struct num *)a;
	struct num *d=(struct num *)b;
	return (c->size > d->size) ?1:-1;
}


int main()
{
	freopen("frac1.in","r",stdin);
	freopen("frac1.out","w",stdout);
	scanf("%d",&n);
	if(n==1)
	{
		printf("0/1\n");
		printf("1/1\n");
		return 0;
	}
	int qwe=0;
	for(int i=2;i<=n;i++)
		for(int j=1;j<i;j++)
		{
			if(check(i,j))
			{
				qwe++;
		    	ku[qwe].aa=j;
		    	ku[qwe].bb=i;
				ku[qwe].size=double(ku[qwe].aa)/ku[qwe].bb;
			}
		}
	qsort(ku+1,qwe,sizeof(ku[0]),cmp);
	printf("0/1\n");
	for(int i=1;i<=qwe;i++)
	{
		if(ku[i].aa!=0)
		{
		    cout<<ku[i].aa<<'/'<<ku[i].bb<<endl;
		}
	}
	printf("1/1\n");
}
int gcd(int a,int b)         
{   if(b==0)  
        return a;  
    else  
       return gcd(b,a%b);  
}  
  
bool check(int a,int b)       
{   if(gcd(a,b)==1) return true;  
    else return false;   
}