对于100%的数据，有S<=2*10*9
题解：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]]); }}
新闻热点
疑难解答
