网页设计与网站建设 1.班级网站. 2.个人主页. 3.求职招聘./semir森马

城市中人们总是拿着号码牌，不停寻找，不断匹配，可是谁也不知道自己等的那个人是谁。

可是燕姿不一样，燕姿知道自己等的人是谁，因为燕姿数学学得好！燕姿发现了一个神奇的算法：假设自己的号码牌上写着数字 S，那么自己等的人手上的号码牌数字的所有正约数之和必定等于 S。

所以燕姿总是拿着号码牌在地铁和人海找数字（喂！这样真的靠谱吗）可是她忙着唱《绿光》，想拜托你写一个程序能够快速地找到所有自己等的人。

Solution

分析约数和的式子(1+p1+p1^2+...+p1^a1)*(1+p2+p2^2+...+p2^a2)*...*(1+pk+pk^2+...+pk^ak)。

本题需要输出所有答案，可以猜测答案不是很多。

我们可以枚举所有的p和他们的指数进行搜索。

我们先定p的范围是根号1e5.

但这样会漏掉很多答案。

观察到大与根号的指数次数最多是一。

所以每次搜的时候判一下有没有大质数。

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#define N  100002
#define NN 100000
using namespace std;
typedef long long ll;
int prime[N],vis[N],s,ans,k,st[N],tot;
bool pd(int x){if(x==1) return false;if(x<=NN) return !vis[x];for(int i=1;i<=tot&&(ll)prime[i]*prime[i]<=x;i++)if(x%prime[i]==0) return false;return true;
}
void dfs(int la,int num,int num1){if(num==1){st[++ans]=num1;return;}if(num-1>prime[la]&&pd(num-1))st[++ans]=(num-1)*num1;for(int i=la+1;i<=tot&&prime[i]*prime[i]<=num;++i)for(ll j=prime[i],t=prime[i]+1;t<=num;j*=prime[i],t+=j){if(num%t==0)dfs(i,num/t,num1*j);}
}
int main(){for(int i=2;i<=NN;++i){if(!vis[i])prime[++tot]=i;for(int j=1;j<=tot&&(k=i*prime[j])<=NN;++j){vis[k]=1;if(i%prime[j]==0)break;}}while(scanf("%d",&s)!=EOF){ans=0;dfs(0,s,1);printf("%d\n",ans);sort(st+1,st+ans+1);if(ans){for(int i=1;i<=ans;++i)printf("%d ",st[i]);printf("\n");}}return 0;
}

#include<iostream>
#include<cstdio>
#include<algorithm>
#define N  100002
#define NN 100000
using namespace std;
typedef long long ll;
int prime[N],vis[N],s,ans,k,st[N],tot;
bool pd(int x){if(x==1) return false;if(x<=NN) return !vis[x];for(int i=1;i<=tot&&(ll)prime[i]*prime[i]<=x;i++)if(x%prime[i]==0) return false;return true;
}
void dfs(int la,int num,int num1){if(num==1){st[++ans]=num1;return;}if(num-1>prime[la]&&pd(num-1))st[++ans]=(num-1)*num1;for(int i=la+1;i<=tot&&prime[i]*prime[i]<=num;++i)for(ll j=prime[i],t=prime[i]+1;t<=num;j*=prime[i],t+=j){if(num%t==0)dfs(i,num/t,num1*j);}
}
int main(){for(int i=2;i<=NN;++i){if(!vis[i])prime[++tot]=i;for(int j=1;j<=tot&&(k=i*prime[j])<=NN;++j){vis[k]=1;if(i%prime[j]==0)break;}}while(scanf("%d",&s)!=EOF){ans=0;dfs(0,s,1);printf("%d\n",ans);sort(st+1,st+ans+1);if(ans){for(int i=1;i<=ans;++i)printf("%d ",st[i]);printf("\n");}}return 0;
}