poj 3090&poj 2478(法雷級数、オラ関数)
http://poj.org/problem?id=3090
法雷級数
フレイ級数の転送式は簡単です.f[1]=2;f[i]=f[i-1]+phi[i]です.
この問題は法雷級数の変形ですよね.答えは2*f[i]-1です.
もっと簡単です.直接に法雷級数を求めます.素数ふるいに基づくオラ関数.
法雷級数
フレイ級数の転送式は簡単です.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
",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
",f[n]-2);
}
return 0;
}