求欧拉函数表题。题意:法雷序列Fn对于任何一个大于等于2的n来说是这么一种序列,它是由最简真分数a/b构成,0 < a < b <= n且a与b互质。现在给你n,求法雷序列Fn里面数的个数。
我的解题思路:水题,对于2~n中每一个数的欧拉函数之和就是答案了。
我的解题代码:
#include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cmath> #include <algorithm> using namespace std; const int N = 1000001; int phi[N]; long long ans[N]; void Init(); void GetPhi(int maxn); int main() { Init(); int n; while (~scanf("%d", &n) && n) { printf("%lld\n", ans[n]); } return 0; } void Init() { memset(phi, 0, sizeof(phi)); phi[1] = 1; GetPhi(N); ans[1] = 0; for (int i=2; i<N; ++i) ans[i] = phi[i] + ans[i-1]; return; } void GetPhi(int maxn) { memset(phi, 0, sizeof(phi)); phi[1] = 1; for (int i=2; i<maxn; ++i) { if (!phi[i]) { for (int j=i; j<maxn; j+=i) { if (!phi[j]) phi[j] = j; phi[j] -= phi[j] / i; } } } return; }