题目描述

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

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

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

输入格式
第一行包含整数N，表示共有N个测试用例。

接下来N行，每行包含一个需要你进行判断的整数X。

输出格式
每个测试用例输出一个结果，每个结果占一行。

如果测试数据是完全数，则输出“X is perfect”，其中X是测试数据。

如果测试数据不是完全数，则输出“X is not perfect”，其中X是测试数据。

数据范围
$ 1≤N≤100 $
$ 1≤X≤108 $

输入样例

3
6
5
28

输出样例

6 is perfect
5 is not perfect
28 is perfect

(数论-试除法求约数)

• 可以先做AcWing 869. 试除法求约数这题
• 找出所有约数，然后累加所有约数（除x自身外），然后判断是否和给定的x相等

时间复杂度

• 试除法求约数的时间复杂度是$O(sqrt(n))$
• 遍历样例每个数是$O(n)$
• 因此时间复杂度是$O(n * sqrt(x))$

C ++ 代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 找出n所有的约数
vector<int> get(int n)
{
    vector<int> res;
    for (int i = 1; i <= n / i; i ++)
    {
        if (n % i == 0)
        {
            res.push_back(i);
            if (n / i != i) res.push_back(n / i);
        }
    }

    sort(res.begin(), res.end());

    return res;
}

int main(){
    int T;
    scanf("%d", &T);

    while(T --)
    {
        int x;
        scanf("%d", &x);
        auto res = get(x);

        int s = 0;
        for (int i = 0; i < res.size() - 1 && s < x; i ++) s += res[i];

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

    return 0;
}