首先是昨天一直wa的fzu 1769代碼:
有運(yùn)行68ms的，膜拜膜拜，不知道怎么寫的，得去學(xué)學(xué)那個(gè)算法。
#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;
}
呵呵，用篩法來(lái)請(qǐng)歐拉函數(shù)還是我一下子冒出來(lái)的想法，嗯，這個(gè)直覺(jué)不錯(cuò)。
不過(guò)一直WA一直WA,原來(lái)是數(shù)據(jù)類型的問(wèn)題。
poj2478也是這個(gè)問(wèn)題，哎哎，以后要多注意數(shù)據(jù)類型這個(gè)東西了！！！
#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……