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

#include <iostream>
#include <fstream>
 
using namespace std;
 
int n,a[100000],b[100000],len=0;
float c[100000];
 
 
void swap(int &x,int &y)
{
     int tmp=x;
     x=y;
     y=tmp;
}
 
int gcd(int x,int y)
{
    if (x>y) swap(x,y);
    if (x==0) return y;
    return (gcd(y%x,x));
}
 
void sort(int l,int r)
{
	
     int i=l,j=r;
     float mid=(float)a[(i+j)/2]/(float)b[(i+j)/2];
     for (;;)
     {
         for (;(float)a[i]/(float)b[i]<mid;i++) {}
         for (;(float)a[j]/(float)b[j]>mid;j--) {}
         if (i<=j)
         {
                  swap(a[i],a[j]);
                  swap(b[i],b[j]);
                  i++;
                  j--;
         }
         if (i>j) break;
     }
     if (l<j) sort(l,j);
     if (i<r) sort(i,r);
}
 
int main()
{
    ifstream fin("frac1.in");
    ofstream fout("frac1.out");
 
    fin>>n;
    len++;
    a[len]=0;
    b[len]=1;
	c[len]=0;
    len++;
    a[len]=1;
    b[len]=1;
	c[len]=1;
    for (int i=2;i<=n;i++)
    {
        for (int j=1;j<=i-1;j++)
        {
            if (gcd(i,j)==1)
            {
                            len++;
                            a[len]=j;
                            b[len]=i;
							c[len]=(float)a[len]/(float)b[len];
            }
        }
    }
	for (int i=1;i<=len;i++)
		for (int j=1;j<=len;j++)
		{
			if (c[j]>c[i])	
			{
				swap(a[i],a[j]);
				swap(b[i],b[j]);
				swap(c[i],c[j]);
			}
		}				  
    for (int i=1;i<=len;i++)
        fout<<a[i]<<"/"<<b[i]<<endl;
    return 0;
}