hdu 2824 The Euler function（歐拉函數）

如果打表的話會超內存，我想到了一種方法解決這個問題。題目給出的數據時3000000，我將三百萬分成300個數據，將整萬的數據存儲下來，計算的時候，先計算x和y之間整萬的數據，然後再計算零散數據。

想法很不錯，但為啥就是通不過呢？而且看提交返回的時間來看，應該是卡在最後一兩組數據上了。

我很疑惑。

代碼中注釋的部分是我之前的代碼。最後這道題竟然是毫無美感的暴力過去了。

#include<stdio.h>
#include<string.h>
#define N 3000005
int a[N];
int b[N];
__int64 c[310];
int main()
{
    int i,j;
    for(i=2;i<N;i++)
        a[i]=i;
    for(i=2;i<N;i++)
    {
        if(b[i]==1)
            continue;
        a[i]=i-1;
        for(j=i+i;j<N;j=j+i)
        {
            b[j]=1;
            a[j]=a[j]/i*(i-1);
        }
    }
    a[1]=a[0]=0;
    c[1]=0;
    __int64 temp;
    c[0]=0;
    j=1;
    temp=0;
    for(i=2;i<N;i++)
    {
        temp+=a[i];
        if(i%10000==0)
            c[j++]=temp;
    }
    int x,y;
    while(scanf("%d%d",&x,&y)!=EOF)
    {
        __int64 sum=0;
        /*
        int x1,y1;
        x1=x/10000;
        y1=y/10000;
        if(x1==y1)
        {
            for(i=x;i<=y;i++)
                sum+=a[i];
        }
        else
        {
            sum+=c[y1]-c[x1];
            for(i=x1*10000+1;i<x;i++)
                sum-=a[i];
            for(i=y1*10000+1;i<=y;i++)
                sum+=a[i];
        }
        */
        for(i=x;i<=y;i++)
            sum+=a[i];
        printf("%I64d\n",sum);
    }
    return 0;
}