BZOJ 3629: [JLOI2014]聪明的燕姿 数论+爆搜

推式子没推出来什么特别有用的结论. 

看题解后发现这尼玛就是一个大爆搜啊. 

以后碰到这种推式子推不出来，或者没啥思路的时候可以考虑爆搜解决. 

code: 

#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>

#define N 50001
#define ll long long
#define MAX 2000000009

using namespace std;

namespace IO {
    void setIO(string s)
    {
        string in=s+".in";
        string out=s+".out";
        freopen(in.c_str(),"r",stdin);
        // freopen(out.c_str(),"w",stdout);
    }
};

int cnt;
int prime[N],vis[N];

int isprime(int x)
{
    if(x<N) return !vis[x];
    for(int i=2;i*i<=x;++i)
        if(x%i==0)  return 0;
    return 1;
}

void Initialize()
{
    int i,j;
    for(i=2;i<N;++i)
    {
        if(!vis[i]) prime[++cnt]=i;
        for(j=1;j<=cnt&&prime[j]*i<N;++j)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)  break;
        }
    }
}

int cn;
int answer[N];

void dfs(int S,int cur,int num)
{
    if(S==1)
    {
        answer[++cn]=num;
        return;
    }
    if(S-1>=prime[cur]&&isprime(S-1))
    {
        answer[++cn]=num*(S-1);
    }
    for(int i=cur;prime[i]*prime[i]<=S;++i)
    {
        int tmp=1+prime[i];
        int now=prime[i];
        for(;tmp<=S;now*=prime[i],tmp+=now)
        {
            if(S%tmp==0) dfs(S/tmp,i+1,num*now);
        }
    }
}

int main()
{
   // IO::setIO("input");
    Initialize();
    int i,j,S;
    while(scanf("%d",&S)!=EOF)
    {
        cn=0;
        dfs(S,1,1);
        printf("%d\n",cn);
        sort(answer+1,answer+1+cn);
        for(i=1;i<cn;++i)  printf("%d ",answer[i]);
        if(cn)  printf("%d\n",answer[cn]);
    }
    return 0;
}