自动搬运

查看原文

来自洛谷，原作者为

	ikunTLE 互关条件见主页（luogu.me/paste/1ij66blw），关注我可以获得我小号 OIerDb 的关注（需私信） || 最后在线时间：2025年8月24日22时12分

搬运于2025-08-24 22:13:32，当前版本为作者最后更新于2024-06-11 21:33:57，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目传送门

思路

本题是一道搜索。

分析过样例后，你会发现从上一次搜下来的数，一直到 $\sqrt{n}$ 中，所有 $n\div i$ 的质因子都接着往下搜，每一个新的质因子就是一个答案。既然那个数是 $n$ 的质因数了，答案就是计数器 $+n-1$（这里的 $n$ 是更新后每一次的 $n\div i$）。

经过排序后就是我们要的答案。

AC CODE

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,ans[N],num;
map<int,bool>mp;
void dfs(int p,int x,int cnt){
	if(x<=p){//没超出答案范围
		int temp=cnt+p-1;
		if(!mp[temp]){//去重
			ans[++num]=temp;
			mp[temp]=true;
		}
	}
	int sqrt_p=sqrt(p);
	for(int i=x;i<=sqrt_p;++i)
		if(!(p%i))//是p（n÷i）的质因子
			dfs(p/i,i,cnt+i-1);//接着搜
	return;
}
int main(){
	scanf("%d",&n);
	dfs(n,2,0);//2是最小的质数，故从2开始
	printf("%d\n",num);
	sort(ans+1,ans+num+1);//排序
	for(int i=1;i<=num;++i)
		printf("%d ",ans[i]);
	return 0;
}