自动搬运

查看原文

来自洛谷，原作者为

	一只大龙猫 嗷~呜！

搬运于2025-08-24 21:07:30，当前版本为作者最后更新于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;
}