法雷序列,法雷级数的求法

1 #include <iostream> 2 #include <cstdio> 3 #include<cstring> 4 using namespace std; 5 const int maxlen=1000010; 6 long long eul[maxlen]; 7 int pri[maxlen],f[maxlen],isprim[maxlen],p=0; 8 inline void get_prim(){ // 线性筛素数 9     memset(isprim,1,sizeof(isprim));10     for(int i=2;i<maxlen;i++){11         if(isprim[i]) pri[p++]=i;12         for(int j=0;j<p && i*pri[j]<maxlen;j++){13             int k=pri[j]*i;14             isprim[k]=0,f[k]=pri[j]; // 得到k的最小素因子15             if(i%pri[j]==0) break;16         }17     }18 }19 inline void get_eul(){20     for(int i=2;i<maxlen;i++)21         if(isprim[i]) eul[i]=i-1;22         else{23             int k=i/f[i];24             if(k%f[i]==0) eul[i]=eul[k]*f[i];25             else eul[i]=eul[k]*(f[i]-1);26         }27     for(int i=3;i<maxlen;i++)28         eul[i]+=eul[i-1];//叠加后求出法雷级数29 }30 int main(int argc, char** argv) {31     int m;32     get_prim();33     get_eul();34     while(scanf("%d",&m) && m)35         printf("%lld\n",eul[m]);36     return 0;37 38 39 }

法雷序列：对任意给定的一个自然数 n,将分母小于 n 的不可约的真分数按上升的次序排列,并且在第 一个分数前加上数 0/1,而在最后一个分数后加上数 1/1,这个序列被称为 n 级法雷序列, 以 Fn 表示.例如,F8 为: 0/1, 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8, 1/1

法雷序列在 acm中常常最为一个考察点，这里在做usaco题目时候出现了这个概念，之前了解过但是没深入学习他的求解过程，今天找了两种求法，一种是枚举排序，比较无耻

另外一种是用dfs，更加无耻。先来介绍下两种算法：

第一种手动写一个分数类，然后枚举构造出 所有的最简分数，最后sort输出，比较好理解

1 /* 2 FROM:USACO 3 PROBLEM:frac1 4 */ 5  6 #include <fstream.h> 7 #include <stdlib.h> 8  9 struct fraction {10     int numerator;11     int denominator;12 };13 14 bool rprime(int a, int b){15    int r = a % b;16    while(r != 0){17        a = b;18        b = r;19        r = a % b;20    }21    return(b == 1);22 }23 24 int fraccompare (struct fraction *p, struct fraction *q) {25    return p->numerator * q->denominator - p->denominator *q->numerator;26 }27 28 int main(){29    int found = 0;30    struct fraction fract[25600];31 32    ifstream filein("frac1.in");33    int n;34    filein >> n;35    filein.close();36 37    for(int bot = 1; bot <= n; ++bot){38        for(int top = 0; top <= bot; ++top){39            if(rprime(top,bot)){40                fract[found].numerator = top;41                fract[found++].denominator = bot;42            }43        }44    }45 46    qsort(fract, found, sizeof (struct fraction), fraccompare);47 48    ofstream fileout("frac1.out");49    for(int i = 0; i < found; ++i)50        fileout << fract[i].numerator << '/' << fract[i].denominator << endl;51    fileout.close();52 53    exit (0);54 }

第二种算法是利用，a/b < a+c / b+d < c/d

每次找出n1/d1 - n2/d2 判断这两个数中间的那个数是否满足题意，如果满足，就从n1/d1- n1+n2 / d1+d2 之间开始判断dfs

判断后再从 n1+n2 / d1+d2 - n2/d2 之间，形成两部分的深度搜索

起始是从0/1-1/1之间的，由此可以得到dfs的代码

转自usaco:

Here's a super fast solution from Russ:

We notice that we can start with 0/1 and 1/1 as our ``endpoints'' and recursively generate the middle points by adding numerators and denominators.

0/1 1/1 1/2 1/3 2/3 1/4 2/5 3/5 3/4 1/5 2/7 3/8 3/7 4/7 5/8 5/7 4/5

Each fraction is created from the one up to its right and the one up to its left. This idea lends itself easily to a recursion that we cut off when we go too deep.

1 /* 2 ID: xvoid191 3 LANG: C++ 4 TASK: frac1 5 */ 6 #include <iostream> 7 #include <cstdio> 8 int N; 9 inline int gcd(int a,int b) {10     for (int r;b!=0;) {11         r=a%b;12         a=b;13         b=r;14     }15     return a;16 }17 18 void dfs(int s,int d,int t,int k) {19     int x=s+t;20     int y=d+k;21     int r=gcd(x,y);22     x/=r;y/=r;23     if (y>N) return;24         printf("dfs-1  %d %d %d %d\n",s,d,x,y);25 26     dfs(s,d,x,y);27 28     printf("%d/%d\n",x,y);29     printf("%d % d% d %d \n",x,y,t,k);30     dfs(x,y,t,k);31 }32 33 int main() {34    // freopen("frac1.in","r",stdin);35 // freopen("frac1.out","w",stdout);36     while (scanf("%d",&N)!=EOF) {37         printf("0/1\n");38         dfs(0,1,1,1);39         printf("1/1\n");40     }41     return 0;42 }

至此，法雷序列求法已经基本掌握了，接下来说法雷级数求法。法雷级数其实就是数N的法雷序列中分数的个数

这个不难求，其实就是从1到n中，每个数与其互质的个数和，即1....n每个数的欧拉函数和+1（0/1,1/1）

欧拉函数我还是会一点滴，就贴一个poj2478的一个高效率的求解办法吧！

原文链接: https://www.cnblogs.com/void/archive/2012/01/19/2327684.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍