法雷数列
定义和定理
定义一： 最简分数（也称既约分数或不可约分数）。若p,q的最大公约数是1，我们称分数p/q是最简分数。
定义二： 真分数，若p,q是正整数，0<p/q<1, 我们说p/q是真分数
定理：
分数a/b, c/d是最简真分数（也可以是0/1或者1/1）且a/b <c/d, 则有
1) 数(a+c)/(b+d)是一个最简分数
2) a/b < (a+c)/(b+d) < c/d
法雷数列的定义：
推导法雷数列方法：
应用定理中的(2),如果 a/b 和 c/d 是一个法雷数列，则在它们中间可以插入 p/q =(a+c)/(b+d),（前提是得出的q值小于或者等于给定的n值）所以可以二分构造，直到不比如
N = 5：
step1: 准备两个数 0/1, 1/1 作为整个法雷数列的第一个元素和最后一个元素0/1, 1/1
step2: 在两个数中间插入1个数1/2, 变为0/1, 1/2, 1/1
step3: 在每对相邻两个数中间插入1个数，变为0/1, 1/3, 1/2, 2/3, 1/1
step4: 在每对相邻两个数中间插入1个数，变为0/1, 1/4, 1/3, 2/5 , 1/2, 3/5, 2/3, 3/4 , 1/1
step5: 0/1 和 1/4 之间 和3/4和 1/1 仍然可插入1个数，且插入的数分母不大于5 0/1, 1/5 , 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5 , 1/1
至此，该序列包含了所有分母不大于5的最简真分数，且各个分数以递增顺序排 列。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define MAXN 8000000 5 using namespace std; 6 int N,t; 7 int ct=2; 8 int tx[MAXN],ty[MAXN]; 9 void farey (int a,int b,int c,int d) 10 { 11 if (b+d > N) return ; 12 /*if (b+d == N) 13 { 14 printf("%d/%d",a+c,b+d); 15 if(a+c != N-1) printf(","); 16 return ; 17 }*/ 18 farey(a,b,a+c,b+d); 19 //printf("%d/%d,",a+c,b+d); 20 tx[ct]=a+c; 21 ty[ct++]=b+d; 22 farey(a+c,b+d,c,d); 23 } 24 int main () 25 { 26 scanf("%d%d",&N,&t); 27 tx[1]=0; 28 ty[1]=1; 29 farey(0,1,1,1); 30 tx[ct]=1; 31 ty[ct]=1; 32 for(int i=1;i<=t;i++) 33 { 34 int m; 35 scanf("%d",&m); 36 if(m>ct) 37 printf("No Solution "); 38 else 39 printf("%d/%d ",tx[m],ty[m]); 40 } 41 return 0; 42 }