Description

Input

Output

Sample Input

Sample Output

HINT

對于100%的數據，有S<=2*10*9

Source

題解：dfs+線性篩

需要用到約數和公式：F(n)=∏(1<=i<=k)[pi^(qi+1)-1)/(pi-1)]

然后對于sqrt(s)以內的素數枚舉，大于sqrt(s)之間判斷，dfs的時候加一些減值和特判即可。

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#define N 100003#define LL long longusing namespace std;int PRime[N],pd[N],n,ans[N],cnt,m;void init(){	for (int i=2;i<=100000;i++) {		if (!pd[i]) prime[++prime[0]]=i;		for (int j=1;j<=prime[0];j++) {			if (prime[j]*i>100000) break;			pd[prime[j]*i]=1;			if (i%prime[j]==0) break;		}	}}bool check(int x){	for (int i=2;i*i<=x;i++) 	 if (x%i==0) return false;	return true;}void dfs(int x,int sum,int num){	if (sum>m&&check(sum-1)) 	 ans[++ans[0]]=num*(sum-1);	if (sum<0) return;	if (sum==1) {		ans[++ans[0]]=num;		return;	}  	int t=num; LL sum1=sum; 	for (int i=x;i<=prime[0];i++) {		if (sum<prime[i]) break;		LL pri=prime[i];		while (true) {			sum1=((LL)pri*prime[i]-1)/(LL)(prime[i]-1);			if (sum%sum1==0) dfs(i+1,sum/sum1,num*pri);			if (sum/sum1<prime[i]) break;			pri*=(LL)prime[i];		}	}}int main(){	freopen("a.in","r",stdin);	freopen("my.out","w",stdout);	init();	while (scanf("%d",&n)!=EOF) {		cnt=0; ans[0]=0; m=ceil(sqrt(n));		dfs(1,n,1);		sort(ans+1,ans+ans[0]+1);		ans[0]=unique(ans+1,ans+ans[0]+1)-ans-1;		printf("%d/n",ans[0]);		for (int i=1;i<ans[0];i++) printf("%d ",ans[i]);		if(ans[0]) printf("%d/n",ans[ans[0]]);	}}