首先是昨天一直wa的fzu 1769代码:
有运行68ms的，膜拜膜拜，不知道怎么写的，得去学学那个算法。
#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;
}
呵呵，用筛法来请欧拉函数还是我一下子冒出来的想法，嗯，这个直觉不错。
不过一直WA一直WA,原来是数据类型的问题。
poj2478也是这个问题，哎哎，以后要多注意数据类型这个东西了！！！
#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;
}
数论刷水题ing……