第3讲4*

#include <iostream>

using namespace std;

int main()
{
    //优化思路：d=2是x=12的约数，那么x/d=6也一定是x=12的约数(成对出现)
    //每次我们枚举较小的一个，满足d<=x/d,即d<=sqrt(x);
    int n;
    cin >> n;
    while(n--)
    {
        int a;
        cin >> a;
        int result = 0;
        for (int i = 1; i * i <= a; i++)
        {
            if(a % i == 0)
            {
               if(i < a) result += i;//约数不取本身（i = a时不取）
               if(i != a/i && a/i < a) result += a/i;//约数不取本身(i'=a/i=a时不取)//且i与a/i不能相同(如36=6*6)
            }
        }
        if(result == a) cout<< a <<" is perfect" <<endl;
        else cout << a <<" is not perfect" <<endl;
    }
    return 0;
}

/*
//本题这么写会time limit exceeded
int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        int a;
        cin >>a;
        int result = 0;
        for (int i = 1; i<a; i++)
        {
            if(a%i == 0) result+=i;
        }
        if(result == a) cout<< a <<" is perfect" <<endl;
        else cout << a <<" is not perfect" <<endl;
    }
    return 0;
}
*/