Question

ACM这道题，为什么超时了？这么短的代码，求解释，谢谢

求特定数的因子和的程序：
#include<stdio.h>

main()
{
long T,N,i;
double sum;
scanf("%ld",&T);
while(T--)
{
sum=0;
scanf("%ld",&N);
for(i=1;i<N;i++)
{
if(!(N%i)) sum+=i;
}
printf("%.0lf\n",sum);
}

}

Answer 1

程序超时跟代码长度没有关系的，while(true)这句话很短吧，但是运行时间是无限长。你这道题找N的因子方法不对，N可能是个很大的数字，比如10亿，你这么找就要循环10亿次，必然超时。一个最简单的优化，只要搜索到N/2就够了，大于N/2的数里面，只有N是它自己的因子，其他数都不可能，你想想是不是呢？当然了，这样写依然要超时的，你自己查一查求整数N所有因子的算法吧，应该找得到，我现在一下也想不起来这个算法怎么写，如果你找不到的话，我晚上试着帮你写一下。

Answer 2

你的复杂度太高了
#include<stdio.h>

main()
{
long T,N,i;
double sum;
scanf("%ld",&T);
while(T--)
{
sum=0;
scanf("%ld",&N);
for(i=1;i*i<=N;i++)
{
if(!(N%i))
{

sum+=i;
if(i*i!=n)
sum+=n/i;
}
}
sum-=n;
printf("%.0lf\n",sum);
}

}

Answer 3

for(i=1;i<=N/2;i++)试试？
或者把sum也改成long试试？整数比浮点数运算快很多哦。