HDU 1215 七夕节
- 题目链接：七夕节
- 题目分析：RT，找出一个数的所有因子的和，水题
- 我的思路：第一眼，数据比较小，那直接遍历吧，应该不会超时。。。 但是评测姬就给我一个TLE让我去思考人生了… Orz
- TLE 代码：
#include<stdio.h>
#include<math.h>
int main(void)
{
int T, N, i, sum;
scanf("%d", &T);
while (T-- > 0)
{
scanf("%d", &N);
sum = 0;
for (i = 1; i <= sqrt(N); i++)
{
if (N%i == 0)
{
sum += i;
if (i != 1 && i != N / i)
sum += N / i;
}
}
printf("%d\n", sum);
}
}
这都TLE了，不应该啊，难道是sqrt()的time complex的问题？ 然后找了找sqrt()的源码，最后在stackoverflow上知道自己错在哪里了。。。。
- sqrt timecomplex(可能需要访问外国网站)；
- 有一个回答是这样的： The problem is that the whole expression i < sqrt(number) must be evaluated repeatedly in the original code, while sqrt is evaluated only once in the modified code. Well, the recent compilers are usually able to optimize the loop so the sqrt is evaluated only once before the loop, but do you want to rely on them ?
- 原因：be evaluated repeatedly, 重复计算，每次都需要进行计算sqrt(N), 所以超时了，按照这个修改代码，就AC了。
- AC代码：
#include<stdio.h>
#include<math.h>
int main(void)
{
int T, N, i, sum;
scanf("%d", &T);
while (T-- > 0)
{
scanf("%d", &N);
sum = 0;
int length = sqrt(N);
for (i = 1; i <= length; i++)
{
if (N%i == 0)
{
sum += i;
if (i != 1 && i != N / i)
sum += N / i;
}
}
printf("%d\n", sum);
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017年09月26日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读