「JLOI2014」聪明的燕姿 - 约数和

题目大意

求出所有约数和为$n$的值$x$

$$f(x)=\sum_{i\mid x}i=n$$

---

初步想法

枚举$x$验证是否约数和为$n$。
求约数和可以使用约数和公式：

$$x=p_1^{a_1}\times p_2^{a_2}\times\cdots\times p_k^{a_k}$$ $$f(x)=\sum_{i=0}^{a_1}p_1^{i}\times\sum_{i=0}^{a_2}p_2^{i}\times\cdots\times\sum_{i=0}^{a_k}p_k^{i}$$

用线性筛预处理$O(\sqrt{n})$内的素数，这么麻烦才能拿到30分。

---

算法优化

稍加思考就可以想到100%的算法。
显然枚举$x$效率太低，我们能否将$x$计算出来？
由公式：

$$n=f(x)=\sum_{i=0}^{a_1}p_1^{i}\times\sum_{i=0}^{a_2}p_2^{i}\times\cdots\times\sum_{i=0}^{a_k}p_k^{i}$$

$n$是一些数的乘积，故可以直接对$n$进行分解。
枚举质数以及其幂，然后递归。
每层Dfs时间复杂度约为$O(\sqrt{Remain})$，$Remain$是尚未分解的$n$的约数乘积。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const long long Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}
bool vst[100005];
long long n,Prime[100005],cnt=0,ans[100005];
void Prime_Table(int n) {
	for(int i=2; i<=n; i++) {
		if(!vst[i])Prime[++cnt]=i;
		for(int j=1; j<=cnt&&Prime[j]*i<=n; j++) {
			vst[Prime[j]*i]=1;
			if(i%Prime[j]==0)break;
		}
	}
}
bool Check_Prime(long long n) {
	if(n==1)return 0;
	for(int i=1; i<=cnt&&Prime[i]<=sqrt(n); i++)
		if(n%Prime[i]==0)return 0;
	return 1;
}
void Dfs(long long Now,int Depth,long long Remain) {
	if(Remain==1) {
		ans[++ans[0]]=Now;
		return;
	}
	if(Remain-1>=Prime[Depth]&&Check_Prime(Remain-1))ans[++ans[0]]=Now*(Remain-1);
	for(int i=Depth; i<=cnt&&Prime[i]<=sqrt(Remain); i++) {
		int sum=1+Prime[i],Pow=Prime[i];
		for(; sum<=Remain; Pow*=Prime[i],sum+=Pow)
			if(Remain%sum==0)Dfs(Now*Pow,i+1,Remain/sum);
	}
}
int main() {
	Prime_Table(100000);
	while(scanf("%lld",&n)!=EOF) {
		ans[0]=0;
		Dfs(1,1,n);
		sort(ans+1,ans+ans[0]+1);
		printf("%lld\n",ans[0]);
		for(int i=1; i<=ans[0]; i++)printf("%lld%c",ans[i],i==ans[0]?'\n':' ');
	}
	return 0;
}