poj2478 ——欧拉函数入门题

April 22, 2013
POJ Math

题目链接：http://poj.org/problem?id=2478 题目大意：　　给你一个数列f(N)，这个数列是由一系列不能约分的分数 a / b (0 < a < b <= n 且 (a,b) = 1)按照递增的顺序排列而成的。输入一个N，求这个数列中元素的个数。题目思路：　　因为题目只需要求出元素的个数，所以，把分母相同的放在一起，然后就发现规律了，其实就是求从2到 n 的欧拉函数的和。范围只有10^6，可以打表预处理。思路很清晰。因为要反复用欧拉函数，所以比较快的方法是用递推的方法求。　　


  for (i = 1; i <= maxn; ++i) f[i] = i;
  for (i = 2; i <= maxn; i+=2) f[i] /= 2;
  for (i = 3; i <= maxn; i+=2){
    if (f[i] == i){
      for (j = i; j <= maxn; j+=i){
        f[j] = f[j] / i * (i - 1);
      }
    }
  }

　　　　这个方法和筛法求素数比较类似，貌似就是那个思想。模拟一下什么就懂了。这里也用到了欧拉函数的性质：φ(n) = n * (1 - 1/p1) * (1 - 1/p2) * …… * (1 - 1/pk)。


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x3f3f3f3f;
const int  MIN =  -0x3f3f3f3f;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};

const int maxn = 1000000+10;
int f[maxn];
int main(void){
#ifndef ONLINE_JUDGE
  freopen("poj2478.in", "r", stdin);
#endif

  LL i, j;
  for (i = 1; i <= maxn; ++i) f[i] = i;
  for (i = 2; i <= maxn; i+=2) f[i] /= 2;
  for (i = 3; i <= maxn; i+=2){
    if (f[i] == i){
      for (j = i; j <= maxn; j+=i){
        f[j] = f[j] / i * (i - 1);
      }
    }
  }
  //printf("%d\n", f[5]);
  //for (i = 2; i <= 14; ++i) printf("f[%d] = %d\n", i, f[i]);
  //for (i = 2; i <= 14; ++i) printf("f[] = %d\n", f[i]);
  int n;
  while (~scanf("%d", &n)){
    if (!n) break; LL ans = 0;
    for (i = 2; i <= n; ++i){
      ans += f[i]; //printf("f[%d] = %d ", i, f[i]);
    }
    printf("%lld\n", ans);
  }

  return 0;
}

　　写代码的时候还是遇到了一些问题，比如把改写成 j 的地方写成了 i ，还好很快找到了，以后这种错误从一开始就不要犯。　　调试的时候发现一个很神奇的现象，不能解释啊。41行的注释，输出来 f[i] 的值都是0！42行的注释输出来就是正常的！好吧，原因到现在我还不知道……貌似是语言的细节？希望神牛路过指点啊~ 　　另外，求的时候，没有必要每次都加一遍，也可以把f[]数组进一步处理，让f[n]保存前n项得欧拉函数的和，这样就可以直接输出f[n]的值了。


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x3f3f3f3f;
const int  MIN =  -0x3f3f3f3f;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};

const int maxn = 1000000+10;
LL f[maxn];
int main(void){
#ifndef ONLINE_JUDGE
  freopen("poj2478.in", "r", stdin);
#endif

  LL i, j;
  for (i = 1; i <= maxn; ++i) f[i] = i;
  for (i = 2; i <= maxn; i+=2) f[i] /= 2;
  for (i = 3; i <= maxn; i+=2){
    if (f[i] == i){
      for (j = i; j <= maxn; j+=i){
        f[j] = f[j] / i * (i - 1);
      }
    }
  }
  for (i = 3; i <= maxn; ++i){
    f[i] += f[i-1];
  }
  //printf("%d\n", f[5]);
  //for (i = 2; i <= 14; ++i) printf("f[%d] = %d\n", i, f[i]);
  //for (i = 2; i <= 14; ++i) printf("f[] = %d\n", f[i]);
  int n;
  while (~scanf("%d", &n)){
    if (!n) break; LL ans = 0;
    /*
    for (i = 2; i <= n; ++i){
      ans += f[i]; //printf("f[%d] = %d ", i, f[i]);
    }
    */
    printf("%lld\n", f[n]);
  }

  return 0;
}

　　速度快了一点儿~这种预处理的方法学习一下。

Read more