farey sequence(朴素构造).cpp

杭电acm解题报告2001---2099.

//TJU 2798.   Farey Sequence 
//TLE
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;
const int NMAX = 3000000;
int total;
int temp1[NMAX],temp2[NMAX],farey1[NMAX],farey2[NMAX];
int * f1[2], * f2[2];

void make_farey_seq(int d)
{
	int i,j,k;
	f1[0] = farey1; f1[1] = farey2;
	f2[0] = temp1; f2[1] = temp2;
	farey1[0] = 0;
	farey2[0] = 1;
	farey1[1] = 1;
	farey2[1] = 1;
	total = 2;

	for(i=2;i<=d;i++) {
		f2[0][0] = f1[0][0];
		f2[1][0] = f1[1][0];
		for(j=1,k=1;j<total;j++) {
			if(f1[1][j-1] + f1[1][j] == i) {
				f2[0][k] = f1[0][j-1] + f1[0][j];
				f2[1][k] = f1[1][j-1] + f1[1][j];
				k ++;
			}
			f2[0][k] = f1[0][j];
			f2[1][k] = f1[1][j];
			k ++;
		}
		total = k;
		int * pre1 = f1[0];
		int * pre2 = f1[1];
		f1[0] = f2[0];
		f1[1] = f2[1];
		f2[0] = pre1;
		f2[1] = pre2;
	}
}

int main() {
	int n,t;
	scanf("%d", &t);
	while(t --) {
		scanf("%d", &n);
		make_farey_seq(n);
		printf("%d/%d", f1[0][1], f1[1][1]);
		int i;
		for(i=2;i<total-1;i++) {
			printf(",%d/%d", f1[0][i], f1[1][i]);
		}
		puts("");
	}
}