完全数

暴力硬写$O(NX)$

事实证明是写不了一点的。。。直接TE.$100$行数据，我才输出$9$个就被迫停止了。。。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;scanf("%d",&n);
    while(n--){
        int a,b=0;cin >> a;
        for(int i = 1;i<a;i++){
            if(a%i == 0) b += i;
        }
        if(a==b)
            printf("%d is perfect\n", a);
        else
            printf("%d is not perfect\n", a);
    }

    return 0;
}

优化，AC的算法

一下两种代码的复杂度都是一样的，但是逻辑大不相同。我无法考证他们一定是一样的。时间复杂度为$O(N\sqrt{X})$

有问题的算法

某些数据可能处理不了，但是哪些情况也可能是一定会避免的（我没办法证明，要对拍一下）。

#include <cstdio>
#include <cmath>
using namespace std;

int main()
{
    int n;scanf("%d",&n);
    while(n--){
        int x,s=0;scanf("%d", &x);
        for(int i = 1;i<sqrt(x);i++){
            if(x%i == 0) s += i+x/i;  // 问题在这里
        }
        s /= 2;  // 问题在这里
        if(x==s)
            printf("%d is perfect\n", x);
        else
            printf("%d is not perfect\n", x);
    }

    return 0;
}

较好的优化解

我不理解？为什么还是要s /= 2;

#include <cstdio>
#include <cmath>
using namespace std;

int main()
{
    int n;scanf("%d",&n);
    while(n--){
        int x,s=0;scanf("%d", &x);
        for(int i = 1;i<sqrt(x);i++){
            if(x%i == 0)
            {
                if(i < x)s += i;
                if(i != x/i && i < x/i) s += x/i;
            }

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

    return 0;
}