题目地址：light oj 1007

第一发欧拉函数。

欧拉函数重要性质：

设a为N的质因数。若(N % a == 0 && (N / a) % a == 0) 则有E(N)=E(N / a) * a；若(N % a == 0 && (N / a) % a != 0) 则有：E(N) = E(N / a) * (a - 1)

对于这题来说。首先卡MLE。。

仅仅能开一个数组。。所以把前缀和也存到欧拉数组里。

然后卡long long。

。要用unsigned long long 。

。

代码例如以下：

#include <iostream>

#include <string.h>

#include <math.h>

#include <queue>

#include <algorithm>

#include <stdlib.h>

#include <map>

#include <set>

#include <stdio.h>

#include <time.h>

using namespace std;

#define LL long long

#define pi acos(-1.0)

#pragma comment(linker, "/STACK:1024000000")

const int mod=9901;

const int INF=0x3f3f3f3f;

const double eqs=1e-9;

const int MAXN=5000000+10;

unsigned LL euler[MAXN];

void init()

{

        int i, j, max1=5000000;

        for(i=2;i<=max1;i++){

                euler[i]=i;

        }

        for(i=2;i<=max1;i++){

                if(euler[i]!=i) continue ;

                for(j=i;j<=max1;j+=i){

                        euler[j]=euler[j]/i*(i-1);

                }

        }

        for(i=2;i<=max1;i++){

                euler[i]=euler[i-1]+euler[i]*euler[i];

        }

}

int main()

{

        int t, l, r, icase=0;

        scanf("%d",&t);

        init();

        while(t--){

                scanf("%d%d",&l,&r);

                printf("Case %d: %llu\n",++icase,euler[r]-euler[l-1]);

        }

        return 0;

}