题目描述

一个整数，除了本身以外的其他所有约数的和如果等于该数，那么我们就称这个整数为完全数。

例如，6就是一个完全数，因为它的除了本身以外的其他约数的和为 1+2+3 = 6。

现在，给定你N个整数，请你依次判断这些数是否是完全数。

算法

约数求和的优化

方法很简单，但是此题直接在[1, n)范围求约数和会报超时。

参考相关代码后注意到，由于公约数总是成对出现，因此求和过程的时间复杂度可以小于O(n)，O(根号n)即可。

还需要在累加中注意的条件有：

1. 当输入为1时，因为求和的约数不包括本身，因此求和结果为0，不是约数；
2. 当索引为1时，1是任何输入的约数满足条件，因此构成一对的另一个约数必为输入整数本身，需要排除。

参考代码

yxc

C++ 代码

#include <iostream>
using namespace std;

int main()
{
    int n,x,s;
    scanf("%d", &n);
    while(n--)
    {
        scanf("%d", &x);
        s=0;
        for(int i=1;i<=x/i;++i)
            {
                if(x%i==0)
                {
                    // 绕过x=1的情况
                    if(i!=x) s += i;
                    // 绕过i=1时，x/i = x 的情况
                    if(x/i!=x) s += x/i;
                }
            }

        if(x==s) printf("%d is perfect\n", x);
        else printf("%d is not perfect\n", x);
    }

    return 0;
}