[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==) return false;

    if(x<=NN) return !vis[x];

    for(int i=;i<=tot&&(ll)prime[i]*prime[i]<=x;i++)if(x%prime[i]==) return false;

    return true;

}

void dfs(int la,int num,int num1){

    if(num==){st[++ans]=num1;return;}

   if(num->prime[la]&&pd(num-))st[++ans]=(num-)*num1;

   for(int i=la+;i<=tot&&prime[i]*prime[i]<=num;++i)

     for(ll j=prime[i],t=prime[i]+;t<=num;j*=prime[i],t+=j){

       if(num%t==)dfs(i,num/t,num1*j);

     }

}

int main(){

    for(int i=;i<=NN;++i){

        if(!vis[i])prime[++tot]=i;

        for(int j=;j<=tot&&(k=i*prime[j])<=NN;++j){

            vis[k]=;

            if(i%prime[j]==)break;

        }

    }

    while(scanf("%d",&s)!=EOF){

    ans=;

    dfs(,s,);

    printf("%d\n",ans);

    sort(st+,st+ans+);

    if(ans){

    for(int i=;i<=ans;++i)printf("%d ",st[i]);printf("\n");

    }

    }

    return ;

}

#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==) return false;

    if(x<=NN) return !vis[x];

    for(int i=;i<=tot&&(ll)prime[i]*prime[i]<=x;i++)if(x%prime[i]==) return false;

    return true;

}

void dfs(int la,int num,int num1){

    if(num==){st[++ans]=num1;return;}

   if(num->prime[la]&&pd(num-))st[++ans]=(num-)*num1;

   for(int i=la+;i<=tot&&prime[i]*prime[i]<=num;++i)

     for(ll j=prime[i],t=prime[i]+;t<=num;j*=prime[i],t+=j){

       if(num%t==)dfs(i,num/t,num1*j);

     }

}

int main(){

    for(int i=;i<=NN;++i){

        if(!vis[i])prime[++tot]=i;

        for(int j=;j<=tot&&(k=i*prime[j])<=NN;++j){

            vis[k]=;

            if(i%prime[j]==)break;

        }

    }

    while(scanf("%d",&s)!=EOF){

    ans=;

    dfs(,s,);

    printf("%d\n",ans);

    sort(st+,st+ans+);

    if(ans){

    for(int i=;i<=ans;++i)printf("%d ",st[i]);printf("\n");

    }

    }

    return ;

}