HDU 2824 简单欧拉函数

1、HDU 2824   The Euler function

2、链接：http://acm.hdu.edu.cn/showproblem.php?pid=2824 

3、总结：欧拉函数

题意：求(a,b)间的欧拉函数值的和。

#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
#include<cstdio>
#define max(a,b) a>b?a:b
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f

const int N=3001000;
int phi[N];

void init()     //欧拉函数,打表模板
{
    for(int i=1;i<N;i++){
        phi[i]=i;
    }
    for(int i=2;i<N;i++){
        if(phi[i]==i){      //首个i就是质数
            for(int j=i;j<N;j+=i){
                phi[j]=phi[j]/i*(i-1);  //i为phi[i]的质因子，每次执行这步，最后即为欧拉函数值
            }
        }
    }
}

int main()
{
    init();
    int a,b;
    LL sum;
    while(scanf("%d%d",&a,&b)!=EOF)
    {
        sum=0;
        for(int i=a;i<=b;i++){
            sum+=phi[i];
        }
        printf("%lld
",sum);
    }

    return 0;
}