http://poj.org/problem?id=3090
法雷级数的递推公式很简单:f[1] = 2; f[i] = f[i-1]+phi[i]。
该题是法雷级数的变形吧,答案是2*f[i]-1。
#include <stdio.h> #include <iostream> #include <map> #include <set> #include <stack> #include <vector> #include <math.h> #include <string.h> #include <queue> #include <string> #include <stdlib.h> #include <algorithm> #define LL long long #define _LL __int64 #define eps 1e-12 #define PI acos(-1.0) using namespace std; const int maxn = 1100; int flag[maxn]; int prime[maxn]; int phi[maxn]; LL f[maxn]; void init() { memset(flag,0,sizeof(flag)); prime[0] = 0; phi[1] = 1; for(int i = 2; i < maxn; i++) { if(flag[i] == 0) { phi[i] = i-1; prime[++prime[0]] = i; } for(int j = 1; j <= prime[0]&&prime[j]*i<maxn; j++) { flag[prime[j]*i] = 1; if(i % prime[j] == 0) phi[prime[j]*i] = phi[i] * prime[j]; else phi[prime[j]*i] = phi[i] * (prime[j] - 1); } } f[1] = 2; for(int i = 2; i <= 1000; i++) f[i] = f[i-1] + phi[i]; } int main() { init(); int test; scanf("%d",&test); for(int item = 1; item <= test; item++) { int x; scanf("%d",&x); printf("%d %d %lld\n",item,x,f[x]*2-1); } return 0; }
http://poj.org/problem?id=2478
更简单了,直接求法雷级数。基于素数筛的欧拉函数。
#include <stdio.h> #include <iostream> #include <map> #include <set> #include <stack> #include <vector> #include <math.h> #include <string.h> #include <queue> #include <string> #include <stdlib.h> #include <algorithm> #define LL long long #define _LL __int64 #define eps 1e-12 #define PI acos(-1.0) using namespace std; const int maxn = 1000010; int flag[maxn]; int prime[maxn]; int phi[maxn]; LL f[maxn]; void init() { memset(flag,0,sizeof(flag)); prime[0] = 0; phi[1] = 1; for(int i = 2; i < maxn; i++) { if(flag[i] == 0) { phi[i] = i-1; prime[++prime[0]] = i; } for(int j = 1; j <= prime[0]&&prime[j]*i<maxn; j++) { flag[prime[j]*i] = 1; if(i % prime[j] == 0) phi[prime[j]*i] = phi[i] * prime[j]; else phi[prime[j]*i] = phi[i] * (prime[j] - 1); } } f[1] = 2; for(int i = 2; i <= 1000010; i++) f[i] = f[i-1] + phi[i]; } int main() { init(); int n; while(~scanf("%d",&n)&&n) { printf("%lld\n",f[n]-2); } return 0; }
poj 3090 && poj 2478(法雷级数,欧拉函数),布布扣,bubuko.com
poj 3090 && poj 2478(法雷级数,欧拉函数)
原文:http://blog.csdn.net/u013081425/article/details/38091321