Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
 Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

这样都超时好像在自己的机器上也慢啊 我都把与当前量有关的欧拉函数都提前求了

Posted by Washington at 2005-07-14 00:15:51 on Problem 2478 
#include <stdio.h> 
#include <string.h> 
#include <math.h> 
#define max 1000000 
#define maxn 10000 

bool c[maxn+1]; 
int a[10],e[max+1],b[maxn+1],f[max+1]; 
__int64 d[max+1]; 

void init() 
{ 
        int i,j,n,t; 

        memset(c,0,sizeof(c)); 
        memset(b,0,sizeof(b)); 

        for (i=4;i<=maxn;i+=2) 
                c[i]=1; 
        n=maxn/3+1; 
        j=0; 
        for (i=2;i<=maxn;i++) 
                if (c[i]==0) 
                { 
                        b[++j]=i; 
                        for (t=i;t<=maxn;t+=i) 
                                c[t]=1; 
                } 
} 

int main() 
{ 
        init(); 
        int i,j,n,s,r,k,t; 

        
        memset(d,0,sizeof(d)); 
        memset(e,0,sizeof(e)); 
        memset(f,0,sizeof(f)); 
        for (i=1;i<=max;i++) 
        { 
              if (f[i]==0) 
              { 
                        memset(a,0,sizeof(a)); 
                        r=0; 
                        n=i; 
                        s=sqrt((double)n)+1; 
                        for (j=1;b[j]<=s;j++) 
                        { 
                                if (n%b[j]==0) 
                                { 
                                        r++; 
                                        a[r]=b[j]; 
                                        while (n%b[j]==0) 
                                                n/=b[j]; 
                                } 
                        } 
                        if (n!=1) 
                        { 
                                r++; 
                                a[r]=n; 
                        } 
                        e[i]=i; 
                        for (t=1;t<=r;t++) 
                                e[i]=e[i]/a[t]*(a[t]-1); 
                        for (t=1;t<=r;t++)
                                for (k=i*a[t];k<=max && k>0;k*=a[t]) 
                                { 
								//	printf("%d\n",k);
                                        f[k]=r;e[k]=e[k/a[t]]*a[t]; 
                                } 
                }
        } 
        d[1]=e[1]=0; 
        d[2]=e[2]; 
        for (i=2;i<=max;i++) 
                d[i]=d[i-1]+e[i]; 
        while (scanf("%d",&n) && n) 
        { 
                printf("%I64d\n",d[n]); 
        } 
        return 0; 
}
Followed by:
Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator