数论+深搜luoguP4397聪明的燕姿

题目背景
阴天傍晚车窗外
未来有一个人在等待
向左向右向前看
爱要拐几个弯才来
我遇见谁会有怎样的对白
我等的人他在多远的未来
我听见风来自地铁和人海
我排着队拿着爱的号码牌

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

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

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

输入输出格式
输入格式：
输入包含 k 组数据。 对于每组数据，输入包含一个号码牌S。

输出格式：
对于每组数据，输出有两行，第一行包含一个整数 m，表示有 m 个等的人。

第二行包含相应的 m 个数，表示所有等的人的号码牌。

注意：你输出的号码牌必须按照升序排列。

一个正整数n可以被分成p1^a1*p2a2p3^a3pn^an;

pi^{ai的正约数个数为ai+1,即1,pi}1,pi^2,pi3,....,pi^ai,所以n的正约数个数为(a1+1)(a2+1)(a3+1)...(an+1);

实际上n的约数是在p1^a1、p2a2、...、pk^ak每一个的约数中分别挑一个相乘得来，

可知共有(a₁+1)(a₂+1)(a₃+1)…(ak+1)种挑法，即约数的个数。

由[乘法原理]可知它们的和为

f(n)=(p1^0+p11+p1^2+…p1a1)(p2^0+p21+p2^2+…p2a2)…(pk^0+pk1+pk^2+…pkak）

于是乎就有了搜索策略，搜索p，并枚举他的幂次，满足一下两个条件即为满足解

①最后分解完，剩余得1，将所得结果记录②分解剩余的数-1是一个质数p，这样就可以看成p^0+p1，也可以得到结果，将其记录
代码如下

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#define LL long long
#include<algorithm>
using namespace std;
int prime[50010],vis[50010],cnt,ans[100010],cnt1;
LL s;
void GetPrime(){
    memset(vis,1,sizeof(vis));
    for(int i=2;i<=50000;i++){
        if(!vis[i]) continue;
        prime[++cnt]=i;
        for(int j=2;j<=50000/i;j++) vis[i*j]=0; 
    }
} 
int check_prime(LL x){
    if(x<=50000&&vis[x]==0) return 0;
    for(int i=1;prime[i]*prime[i]<=x;i++) if(x%prime[i]==0) return 0;
    return 1;
}
void dfs(LL now,int last,LL left){
    if(left==1){//情况1
        ans[++cnt1]=now;
        return;
    }
    if(left-1>prime[last]&&check_prime(left-1)) ans[++cnt1]=now*(left-1);//情况2
    for(int i=last+1;prime[i]*prime[i]<=left;i++) 
        for(LL temp=prime[i]+1,t=prime[i];temp<=left;t*=prime[i],temp+=t) if(left%temp==0) dfs(now*t,i,left/temp);      
}
int main(){
    GetPrime();
    while(scanf("%lld",&s)!=EOF){
        cnt1=0;
        dfs(1,0,s);
        sort(ans+1,ans+cnt1+1);
        printf("%d\n",cnt1);
        for(int i=1;i<=cnt1;i++){
            if(i==cnt1) printf("%d\n",ans[i]);
            else printf("%d ",ans[i]);
        }
    }
    return 0;
}