题目链接:http://acm.sdibt.edu.cn/JudgeOnline/problem.php?id=1185

题目超简单,但普通求法超时(WA了好几次,羞愧啊),打表法较快,现在知道打表的优点了……

代码:

#include <stdio.h>
#include <math.h>
int a[500000];
int main()
{
int T,n,i,j;
a[1]=0;
for(i=2;i<=500000;i++)
a[i]=1;
for(i=2;i<=sqrt(500000);i++)
{
a[i*i]+=i;
for(j=i+1;j<500000/i;j++)
a[i*j]+=i+j;
}
scanf(“%d”,&T);
for(i=0;i<T;i++)
{
scanf(“%d”,&n);
printf(“%d\n”,a[n]);
}
return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation