solution

题意：求所有 $i$，使$\sigma_i = n , n\leq 10^9$。$\sigma$ 为因子和函数。

显然 $i,1$ 都是 $i$ 的因子，所以满足条件的数一定小于 $n$。

由于 $\sigma_n = \prod {(1+p_i+p_i^2+....+p_i^{a_i})}$ ，考虑对 $n$ 搜索可行的因子，来拼凑出满足条件的数。

具体地，令 dfs(now,s,t) 表示当前 $n$ 还剩下 $now$，考虑到第 $s$ 个质数，当前累乘的结果是 $t$。

显然当 $now=1$ 时 $t$ 就是一个答案。

考虑一种特殊情况：$n-1$ 是一个答案，且是一个大质数，这时我们需要特判这种情况。

其他情况 $n$ 一定有一个小于等于 $\sqrt{n}$ 的因子，所以只用预处理小于等于 $\sqrt{n}$ 的质数。

直觉来看答案不会太多，所以这个搜索大抵是不会超时的。

场上想到了，但因为写的太勾石了没调出来

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
int T,n,m;
int N=1e5,tot=0;
int minp[101000],pri[101000];
void getpri(){
	for(int i=2;i<=N;i++){
		if(!minp[i]) pri[++tot]=i,minp[i]=i;
		for(int j=1;pri[j]<=minp[i]&&i*pri[j]<=N;j++){
			minp[i*pri[j]]=pri[j];
			if(i%pri[j]==0) break;
		}
	}
}
int isprime(int x){
	if(x<=1e5) return x==minp[x];
	for(int i=1;pri[i]<=sqrt(x);i++){
		if(x%pri[i]==0) return 0;
	}
	return 1;
}
vector<int> ans;
void dfs(int now,int s,int t){
	if(now==1){ans.push_back(t);return;}
	if(now>pri[s]&&isprime(now-1)) ans.push_back(t*(now-1));
	for(int i=s;pri[i]<=sqrt(now);i++){
		int r=pri[i]+1,p=pri[i];
		for(int j=1;r<=now;j++){
			if(now%r==0) dfs(now/r,i+1,t*p);
			p*=pri[i],r+=p;
		}
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	getpri();
	while(cin>>n){
		ans.clear();
		dfs(n,1,1);
		sort(ans.begin(),ans.end());
		cout<<ans.size()<<'\n';
		for(int i=0;i<ans.size();i++) cout<<ans[i]<<' ';
		if(ans.size()) cout<<'\n';
	}
	return 0;
}

跑的飞快。