frac1.cpp

USACO chapter two.Useful for beginners.

/*
ID: chenkai4
PROG: frac1
LANG: C++
*/
#include <stdio.h>

int N;

int gcd(int a,int b)
{
	if(a<b)
	{
		int t;
		t=a;a=b;b=t;
	}
	int r;
	do
	{
		r=a%b;
		a=b;
		b=r;
	}while(r);
	return a ;
}

double num[160*160];int nums=0;
int x[160*160],y[160*160];

#define PUSH(A,B) {sl[sp]=A;sr[sp]=B;sp++;}
#define POP(A,B) {sp--;A=sl[sp];B=sr[sp];}
void Quicksort(int l,int r,bool up)
{
	static int sl[160*160], sr[160*160], sp;
	int i,j,t;double p,dt;
	sp=0;
	PUSH(l,r);
	while(sp)
	{
		POP(l,r);
		i=l;j=r;p=num[(i+j)/2];
		while(i<=j)
		{
			if(up)
				{while(num[i]<p)i++;while(num[j]>p)j--;}
			else
				{while(num[i]>p)i++;while(num[j]<p)j--;}
			if(i<=j)
			{
				dt=num[i];num[i]=num[j];num[j]=dt;
				t=x[i];x[i]=x[j];x[j]=t;
				t=y[i];y[i]=y[j];y[j]=t;
				i++;j--;
			} 
		}
		if(l<j)PUSH(l,j);
		if(i<r)PUSH(i,r);
	}
}



int main()
{
	freopen("frac1.in","r",stdin);
	freopen("frac1.out","w",stdout);
	scanf("%d",&N);
	printf("0/1\n");
	for(int a=1;a<=N;a++)
	{
		for(int b=1;b<a;b++)
		{
			if(gcd(a,b)==1)
			{
				num[++nums]=(double)b/(double)a;
				x[nums]=b;
				y[nums]=a;
			}
		}
	}
	Quicksort(1,nums,true);
	for(int a=1;a<=nums;a++)
		printf("%d/%d\n",x[a],y[a]);
	printf("1/1\n");
	return 0;
}