?
法雷级数的递推公式很简单：f[1] = 2; f[i] = f[i-1]+phi[i]。
该题是法雷级数的变形吧，答案是2*f[i]-1。
#include #include #include #include #include #include #include #include #include #include #include #include #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 ? http://poj.org/problem?id=2478 更简单了，直接求法雷级数。基于素数筛的欧拉函数。 ? #include #include #include #include #include #include #include #include #include #include #include #include #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 ? ? ?
http://poj.org/problem?id=2478
更简单了，直接求法雷级数。基于素数筛的欧拉函数。
#include #include #include #include #include #include #include #include #include #include #include #include #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 ? ? ?