 |
| ||||
Home Page
F.A.Qs
Statistical Charts
Past Contests
Scheduled Contests
Award Contest
| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
这题卡时很历害，能省时就省吧In Reply To:这样都超时好像在自己的机器上也慢啊 我都把与当前量有关的欧拉函数都提前求了 Posted by:Washington at 2005-07-14 00:15:51 > #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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator
