Question

杭电http://acm.hdu.edu.cn/showproblem.php?pid=1215这道题的解题思路是什么

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
int n,n1,i;
cin>>n;
while(n!=0)
{
n--;
cin>>n1;int s=0;
for(i=2;i<=sqrt(float(n1));i++)
{
if(n1%i==0)
{
if(i*i==n1)s=s+i;
else
{
s=s+(n1/i+i);
}
}
}
cout<<s+1<<endl;
}
return 0;
}
为什么我的这个会超时
一定要用下面的程序，但其解题思路是什么
#include <stdio.h>
#
define N 500000
；
long a[500001];
void main()

{
long i,j,m,n;

a[1]=0;
for(i=2;i<=N;i++)
a[i]=1;

for(i=2;i<=N/2;i++)

{

for(j=2;j*i<=N;j++)
a[j*i]+=i;

}
scanf("%ld",&n);

for(i=1;i<=n;i++)

{
scanf("%ld",&m);
printf("%ld\n",a[m]);

}

}

Answer 1

ls说的没错
首先你一定要避免使用cin和cout，这对于比赛来说太慢了
特别是数据很多（比如十万组），你有可能在读数据的时候就已经TLE了
另外，预处理一般来说是这样的：
1、答案是有限的、确定的、可存储的
2、计算全部答案并不会浪费比读一组数据算一组数据再乘以组数要的时间多（这句话可能有点难以理解，你可以理解成查询次数非常多，但是全部答案不是很多。比如说素数表，你这题就是一个很典型的筛法，就是一个很好的预处理，还有一种技术叫做"打表"，也是一种预先存储答案的行为）
3、当输入数据之后，直接以O(1)的时间给出答案

Answer 2

预处理，还有scanf读入比cin快，数据很多的情况下可以减少很多时间

追问

什么预处理？？？

追答

就是你在读入数据前，对数据进行处理，然后读入数据就可以输出结果了