[JLOI2014]聪明的燕姿（搜索）

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

可是燕姿不一样，燕姿知道自己等的人是谁，因为燕姿数学学得好！燕姿发现了一个神奇的算法：假设自己的号码牌上写着数字 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
",ans);
    sort(st+1,st+ans+1);
    if(ans){
    for(int i=1;i<=ans;++i)printf("%d ",st[i]);printf("
");
    }
    }
    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
",ans);
    sort(st+1,st+ans+1);
    if(ans){
    for(int i=1;i<=ans;++i)printf("%d ",st[i]);printf("
");
    }
    }
    return 0;
}