记录编号	35804	评测结果	AAAAAAAAAAA
题目名称	法雷序列	最终得分	100
用户昵称	QhelDIV	是否通过	通过
代码语言	C++	运行时间	0.061 s
提交时间	2012-03-03 09:18:27	内存使用	2.86 MiB

#include <fstream>
#include <cstdlib>
using namespace std;
ifstream fin("frac1.in");
ofstream fout("frac1.out");

int n,m;
class A
{
public:
	double Data;
	int f,s;
}Frac[170000];

int gcd(int i,int j)
{
	if(j!=0)
		return gcd(j,i%j);
	else
		return i;
}

void Initialize()
{
double i,j;
	fin>>n;
	for(i=1;i<=n;i++)
		for(j=1;j<i;j++)
			if(gcd(i,j)==1)
			{
				Frac[++m].Data=j/i;
				Frac[  m].f   =j;
				Frac[  m].s   =i;
			}
}

int Cmp(const void *p,const void *q)
{
	if(((A*)p)->Data - ((A*)q)->Data>0)
		return 1;
	else
		return -1;
}

int main()
{
	Initialize();
	
	qsort(Frac+1,m,sizeof(A),Cmp);
	
	fout<<"0/1"<<endl;
	for(int i=1;i<=m;i++)
		if(Frac[i].Data!=Frac[i-1].Data && Frac[i].Data!=Frac[i+1].Data)
			fout<<Frac[i].f<<'/'<<Frac[i].s<<endl;
	fout<<"1/1"<<endl;
	fin.close();
	fout.close();
}