poj 3090 && poj 2478（法雷级数，欧拉函数）

http://poj.org/problem?id=3090

法雷级数

法雷级数的递推公式非常easy：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;

}

更简单了，直接求法雷级数。基于素数筛的欧拉函数。

#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;

}