题目描述
//725. 完全数
样例
算法1
(暴力枚举) $O(n*m)$
就是普通循环代码,但是该复杂度高达100*1e+8=1e+10, O(100亿),所以会一直报错时间超时;
需要更改内循环迭代条件才能优化。
内循环参考了 ACWING 同学ID <第一WA者金银花 > 的思路,我在这里解释了一下
算法2 优化后 C++ 代码
#include <cstdio>
using namespace std;
int main(){
int n;//n为测试次数,x为数据
scanf ("%d",&n);
for (int i = 0 ; i < n ; i++){
int sum = 1; //约数求和,将首数字自动加上
int x ;
scanf("%d",&x);
for ( int j = 2 ; j <= x/j ; j++){//i相当于一个约数,n/i相当于另外一个约数;i逐渐增加,n/i逐渐减少,很显然当i>n/i时候会倒过来重新来一遍,是没必要的;
//单调性保证了正确性;这样能降低很大的时间复杂度。
if ( x % j == 0 ) sum = sum + j + x/j ;
if ( sum > x ) break;
}
if (sum == x && sum != 1) printf("%d is perfect\n", x);//注意1不是完全数
else printf("%d is not perfect\n", x);
}
return 0;
}