首先是昨天一直wa的fzu 1769代碼:
有運行68ms的，膜拜膜拜，不知道怎么寫的，得去學(xué)學(xué)那個算法。
#include<stdio.h>
#include<string.h>
#include<math.h>
long long p[3000005];
int GetEula()
{
int i,j;
for (i=1;i<=3000000 ;i++ )
p[i]=i;
p[1]=0;
i=2;
while (i<3000000)
{
while (p[i]<i) i++;
j=i;
while (j<=3000000)
{
p[j]=p[j]*(i-1)/i;
j+=i;
}
}
}
int main()
{
int i,a,b;
long long s;
GetEula();
while (scanf("%d%d",&a,&b)==2)
{
s=0;
while (a<=b)
s+=p[a++];
printf("%I64d\n",s);
}
return 0;
}
呵呵，用篩法來請歐拉函數(shù)還是我一下子冒出來的想法，嗯，這個直覺不錯。
不過一直WA一直WA,原來是數(shù)據(jù)類型的問題。
poj2478也是這個問題，哎哎，以后要多注意數(shù)據(jù)類型這個東西了！！！
#include<stdio.h>
#include<string.h>
#include<math.h>
long long p[3000005];
int GetEula()
{
int i,j;
for (i=1;i<=3000000 ;i++ )
p[i]=i;
p[1]=0;
i=2;
while (i<3000000)
{
while (p[i]<i) i++;
j=i;
while (j<=3000000)
{
p[j]=p[j]*(i-1)/i;
j+=i;
}
}
}
int main()
{
int i,n;
long long s;
GetEula();
while (scanf("%d",&n)==1&&n)
{
s=0;
while (n)
s+=p[n--];
printf("%I64d\n",s);
}
return 0;
}
數(shù)論刷水題ing……