题目大意：

给出n，m，你需要求出从n到m所有欧拉函数的值。

思路：

先看代码吧。。。。

代码：

#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>#define N 3000010using namespace std;int n,m;long long ans,phi[N];void get_phi(){    phi[1]=0;    for(int i=2;i<=N;++i)    {        if(i&1) phi[i]=i;        else phi[i]=i/2;    }    phi[2]+=phi[1];    for(int i=3;i<=N;i+=2)    {        if(phi[i]==i)          for(int j=i;j<=N;j+=i)            phi[j]=phi[j]/i*(i-1);        phi[i]+=phi[i-1],phi[i+1]+=phi[i];    }}int main(){    get_phi();    while(~scanf("%d%d",&n,&m))    {        ans=phi[m]-phi[n-1];        printf("%lld\n",ans);    }    return 0;}

哈哈，看不明白对吧

显然，我也看不明白。。。。

好了，大体说说吧。 我们还是用欧拉函数来解这道题（废话(#‵′)凸）

但是我们显然不能直接暴力枚举（为什么？？）（T成狗啊！！！！）可能您写的好看说不定就过了是吧（虽然不大可能吧。。。。因为有多组数据啊（无奈   ）），反正我是T成狗了。。。。

既然这样不行，那我们就找个方便一点的做法。这是有的大佬就想到了，要不我们打个欧拉函数表吧（说白了就是打个表，用个数组把每个欧拉函数值都存起来）（蒟蒻头一回听说这个东西，长见识），不过好像还是T。。。。因为我们有多组数据，对于每一组数据我们都要o（n）查询

我们再找个方便一点的做法，要不我们用一个前缀和吧。（欸，好像可行。。。）这样我们就只需要处理一次，再对于每一组询问o(1)查询就好了

当然又有人要问了，怎么处理？？　　　　这个。。。。蒟蒻表示也不太懂，但我还是尽量说明白吧（若果有明显错误的地方，请不要听我瞎bibi）

首先我们先把数据处理到N（为什么？？ 因为这样我们可以只处理一次，减小时间复杂度啊。 可是这样我们不就多处理了很多吗？？那时间复杂度不是更高了吗？？　　ORZ，因为我们是有多组数据啊，我们不知道他最大的m是几啊，省得我们再对于每一组询问都要处理一次了），对于循环到的数，我们先判断她是奇数还是偶数，如果是偶数的话，那么就先把他的欧拉函数值附成i/2（为什么？？　　你看啊，2的欧拉函数值是不是1,4的欧拉函数值是不是2,6的欧拉函数值是不是2,8的欧拉函数值是不是4.。。。。。。这样是不是就可以推出n（为偶数）的欧拉函数值一定比n/2小　　好吧，我们可以这样想，偶数一定与偶数不互质，那么我们就排除了n/2个数）如果是奇数的话我们就把他的欧拉函数值附成i，接下来我们再进行一遍循环，来筛掉与每个数不互质的数的个数。

  for(int i=3;i<=N;i+=2)//这个地方我们只循环奇数，因为对于偶数我们前面已经把与他一定不互质的数（偶数）排除了，那么如果    {　　　　　　　　　　　//这个数还有与她不互质的数，那么这个最大公约数一定是奇数，不然一定早被筛掉了。。。。。        if(phi[i]==i)//如果这个数没有被处理过          for(int j=i;j<=N;j+=i)//跟欧拉筛一样是每个数都被他最小的因子所筛去            phi[j]=phi[j]/i*(i-1);//欧拉函数公式        phi[i]+=phi[i-1],phi[i+1]+=phi[i];//计算前缀和    }

 应该明白了吧。。。。