学步园

题目链接：点击打开链接

题意很简单：求a到b之间所有数的欧拉值。

递推求数据范围内的所有的欧拉值。求一个前缀数组。直接取值就好。

跪求62MS大神的解法。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define LL __int64

const int N=3*1e6+7;
LL e[N];
void Euler2(){
    LL i,j;
    for(i=1;i<=N-7;i++) e[i] = i;
    for(i=2;i<=N-7;i+=2) e[i] /= 2;
    for(i=3;i<=N-7;i+=2)
    if(e[i]==i){
        for(j=i;j<=N-7;j+=i)
        e[j]=e[j]/i*(i-1);
    }
    for(int i=2;i<=N-7;i++)
    e[i]+=e[i-1];
}

int main(){
    Euler2();
    LL a,b;
    while(~scanf("%I64d%I64d",&a,&b)){
        printf("%I64d\n",e[b]-e[a-1]);
    }
    return 0;
}