poj 2478（欧拉函数打表）

题目链接：http://poj.org/problem?id=2478

题意：求法雷级数Fn中有多少个分数

法雷级数Fn定义：

　　　　　　F₂ = {1/2}

　　　　　　F₃ = {1/3 , 1/2 , 2/3}

                    F₄ = {1/4 , 1/3 , 1/2 , 2/3 , 3/4}

                    F₅= {1/5 , 1/4 , 1/3 , 2/5 , 1/2 , 3/5 , 2/3 , 3/ 4 , 4/5}

思路：很明显答案是分别 找2,3.....n中欧拉函数之和。

 我们会想到跑一遍所有的欧拉函数，再前缀和。但是n是10⁶，用时间复杂度O(n√n)求每个数的欧拉函数是会超时的。

这里有一个时间复杂度约O(nln n）的递推求欧拉函数。

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

思路就是，当φ(n)=n-1时，n是素数。所以在遍历过程中如果遇到欧拉函数等于自身的,那么说明该数是素数，把这个数的欧拉函数改变，

同时也把该素因子整除的数改变。

代码中是先令欧拉函数等于本身，先将偶数筛掉一个素因子2。  现在素数只可能大于2的奇数，再直接筛奇数，将它的倍数中的这个素因子筛掉，这里和一般的一样 乘以 (i-1)/i。所以会找所有素数，且每个数都会筛掉自己的所以素因子，从而得到欧拉函数。

 完整代码：

#include<stdio.h>
#include<string.h>
typedef long long ll;
ll ph[1000010];
int main()
{
    for(int i=1;i<1000010;i++)
        ph[i]=i;
    for(int i=2;i<1000010;i+=2) 
        ph[i]=i/2;
    for(int i=3;i<1000010;i+=2)//打表 
    {
        if(ph[i]==i)
        {
            for(int j=i;j<1000010;j+=i)
                ph[j]=ph[j]/i*(i-1);
        }
    }
    for(int i=3;i<1000010;i++)//前缀和 
        ph[i]+=ph[i-1];
    ll n;
    while(scanf("%lld",&n)!=EOF&&n)
    {
        printf("%lld
",ph[n]);
    }    
    return 0;
}