AcWing 725. 完全数

AcWing 725. 完全数

1. 地址

    https://www.acwing.com/problem/content/description/727/

2. 题解

#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

// 注意：这道题如果暴力解法一定TLE
// 因此，我们需要对其进行优化
int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        long number;
        scanf("%ld",&number);
        long sum = 0;
        //设i为第一个约数，那么number/i就为另外一个约数(最后一个)
        //因此我们只需要从i<=number/i的范围找约数即可
        //对上面的式子进行简化，可以得到i²<=number
        //进而i<=sqrt(number)
        for(int i=1;i<=sqrt(number);i++){
            //排除掉1,1的约数是1,题目要求排除本身
            if(number == 1){
                break;
            }
            //i是约数
            if(number % i == 0){
                 sum += i;
                //排除掉因数是本身的情况
                if(number / i == number){
                    continue;
                }else if(i == number / i){          //排除掉两个因数相等，从而重复计算的情况
                    continue;
                }else{
                    sum += number / i;
                }
            }
        }
        if(number == sum){
            printf("%ld is perfect\n",number);
        }else{
            printf("%ld is not perfect\n",number);
        }
    }
    return 0;
}