难点:暴力解法的优化问题
由题中数据范围可知,最大测试数据时间可达10的8次方*100 是100亿,超过了1亿一定是超时了
思路:比如要找出12的完全数,若其中一个完全数为2,就一定能找到另一个完全数6,所以只需考虑根号12的循环量.
注意:①考虑x=1不是完全数的特例②当约数相同只需要加一次
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
int x,n;
int s = 0;
cin >> n;
for(int i = 1; i <= n;i++)
{
cin >> x;
for(int j = 1;j * j <= x;j++)
{
if(x % j == 0){
if(j < x) s += j; //先加较小约数且包括x=1的特例情况
if(x / j < x && j != x / j) s += x / j; //再加另一个约数
}
}
if(s == x) printf("%d is perfect\n",x);
else printf("%d is not perfect\n",x);
s = 0;
}
return 0;
}