HDU 1215 七夕节

r囧r小猫 2021-12-24 08:55 294阅读 0赞

*  题目链接：[七夕节][Link 1]
 *  题目分析：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][](可能需要FQ)；
 *  有一个回答是这样的：  
    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);
        }
    }

转载于:https://www.cnblogs.com/FlyerBird/p/9052559.html

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=1215
[sqrt timecomplex]: https://stackoverflow.com/questions/30612699/sqrt-time-complexity-comparison