自动搬运

查看原文

来自洛谷，原作者为

	Pioneer 退役了家人们||愿为逝者哀哭，泣下如雨，充盈渡川……如潮涌至，领你归乡。||原/崩/绝/王者/CODM/CR/CF/MC/CS的集大成者

搬运于2025-08-24 21:17:40，当前版本为作者最后更新于2025-02-25 20:20:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题第一感觉就是暴力，即枚举从１到 $n+1$ 作为除数的商。

#include<bits/stdc++.h>
using namespace std;
long long t,n,a[10000000];
int main()
{
	scanf("%lld",&t);
	while(t--){
		scanf("%lld",&n);
		int p=1,cnt=0;
		for(int i=n+1;i>=1;i--){
			int k=n/i;
			if(k==p)continue;
			else a[++cnt]=k,p=k;
		}
		cout<<cnt<<endl;
		for(int i=1;i<=cnt;i++)cout<<a[i]<<" ";
		cout<<endl;
	}
    return 0;
}

然而，不出意外，TLE了一半。

所以优化是本题的关键。枚举的时候可以联想到判断一个数是否为素数时，仅需枚举到 $\sqrt{n}$。

同理，此题我们处理除数时，枚举到 $i$ 时，同时将 $n/i$ 压入数组内，枚举到 $\sqrt{n}$ ，最后再用 sort 排列一下就行了。（需要注意当 $n$ 为完全平方数时仅需压入一个）

完整代码

#include<bits/stdc++.h>
using namespace std;
long long t,n,a[10000000];
int main()
{
	scanf("%lld",&t);
	while(t--){
		scanf("%lld",&n);
		int cnt=1;
		a[cnt]=0;
		for(int i=1;i<=sqrt(n);i++){
			if(n/i==i)a[++cnt]=i;
			else {a[++cnt]=i;a[++cnt]=n/i;}
		}
		sort(a+1,a+cnt+1);
		cout<<cnt<<endl;
		for(int i=1;i<=cnt;i++)cout<<a[i]<<" ";
		cout<<endl;
	}
    return 0;
}