题目描述

725.完全数

最初想法（不可取）

Time Limit Exceeded

扫描每一个数值，会TLE。因为100*10^8，超过C++每秒一亿次计算的上限。

C++ 代码

#include<iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    while(n--){
        int x;
        cin>>x;
        int s=0;//和
        for(int i=1;i<x;i++){
            if(x%i==0)
                s+=i;
        }
        if(s==x)
            cout<<x<<" is perfect"<<endl;
        else if(s!=x)
            cout<<x<<" is not perfect"<<endl;

    }
    return 0;
}

进一步优化

思路

约数都是成对出现，如果x可以被d整除，那么也可以被x/d整除。
我们只需要枚举较小的那个，d<=x/d，即d^2<=x，得到d<=sqrt(x)
100*10^8开根号为10000，不超过限制。

C++ 代码

#include<iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    while(n--){
        int x;
        cin>>x;
        int s=0;//和
        for(int i=1;i*i<=x;i++){
            if(x%i==0){
                if(i<x)s+=i;
                if(i!=x/i&&x/i<x)s+=x/i;
            }
        }
        if(s==x)
            cout<<x<<" is perfect"<<endl;
        else if(s!=x)
            cout<<x<<" is not perfect"<<endl;

    }
    return 0;
}