B2127 求正整数 2 和 n 之间的完全数 题解

一只大龙猫 · 2021-07-03 21:06:08 · 题解

原题传送门

对于这道题，我们可以打表做。

数据生成器如下：

#include<iostream>
using namespace std;
bool check(int x){
    int sum=0;
    for(int i=1;i*i<=x;i++){//从1枚举到x的平方根就可以了，降低时间复杂度。 
        if(x%i==0){
            sum+=i;
            if(i*i!=x)sum+=x/i;//因为如果i是x的因数，则x/i也是x的因数。
            //但是如果x是平方数的话，则x的平方根会被重复计算，须加上特判。 
        }
    }
    return sum-x==x;
    //因为sum-x==x本身就是布尔表达式，所以可以直接返回。 
}
int main(){
    for(int i=2;i<=10000;i++){
        if(check(i))cout<<i<<endl;
    }
    return 0;
}

时间复杂度为 O(n \sqrt n)。

结果如下：

（我不会告诉你，在百度百科里也能找到这个表……）

有了数据，我们便可以打表了：

#include<iostream>
using namespace std;
int n;
int main(){
    ios::sync_with_stdio(0);
    cin>>n;
    if(n>=6)cout<<"6"<<endl;
    if(n>=28)cout<<"28"<<endl;
    if(n>=496)cout<<"496"<<endl;
    if(n>=8128)cout<<"8128"<<endl;
    return 0;
}