题目背景

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

题目描述

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

可是燕姿不一样,燕姿知道自己等的人是谁,因为燕姿数学学得好!

燕姿发现了一个神奇的算法:

假设自己的号码牌上写着数字$S$,那么自己等的人手上的号码牌数字的所有正约数之和必定等于$S$。

所以燕姿总是拿着号码牌在地铁和人海找数字。

可是她忙着唱《绿光》,想拜托你写一个程序能够快速地找到所有自己等的人。

输入格式

输入包含$k$组数据。 对于每组数据,输入包含一个号码牌$S$。

输出格式

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

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

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

样例输入

42

样例输出

3
20 26 41

数据范围

对于$100\%$的数据,$k≤100, S≤2×10^9$ 。

菜鸡的咆哮

对于一个数$N$,如果它的标准分解式为$N=p_1^{a_1}p_2^{a_2}p_3^{a_3}…p_n^{a_n}$

那么约数和$S=\begin{matrix} \prod_{i=1}^n \end{matrix}\begin{matrix} \sum_{j=0}^{a_i} {p_i}^j \end{matrix}$

现在知道了$S$,要求所有约数和为$S$的数。

可以考虑枚举公式中的的$p_i$与其指数$j$。

但数据中$S_{max}=2×10^9$,显然不可能筛出$1-2×10^9$中的所有质数。

对于一个正整数$N$,其$\geq\sqrt N$的所有质因数的指数一定为1

所以我们可以只筛出$\leq\sqrt N$的质数来搜索。

在搜索中,我们令$n$的初值为待搜索的因数和,$num$为数。

根据因数和的公式,每次枚举完当前质因子$p$的指数$k$后,

我们将$n/ \sum_{j=0}^{a_i} {p_i}^j $递归到下一层,当$n=1$即得到答案$num$。

特别的,如果$n-1>=prime[step]$并且$n-1$为质数,

我们可以确保$num\times (n-1)$的约数和一定为$N$,统计答案。

代码

#include<bits/stdc++.h>
#define ll long long
#define maxm 100005
using namespace std;
inline int read(){
    char ch=getchar();int s=0,w=1;
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+ch-48;ch=getchar();}
    return s*w;
}
int n;
int cnt=0;
int vis[maxm];
int prime[maxm];
void euler(){
    memset(vis,0,sizeof(vis));
    for(int i=2;i<maxm;i++){
        if(vis[i]==0) prime[++cnt]=i;
        for(int j=1;j<=cnt&&i*prime[j]<maxm;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
}
bool isprime(int x){
    if(x==1) return false;
    for(int i=2;i*i<=x;i++){
        if(x%i==0) return false;
    }
    return true;
}
int ans;
ll xx[maxm];
void dfs(int step,int n,ll num){
    if(n==1){
        xx[++ans]=num;
        return;
    }
    if(n-1>=prime[step]&&isprime(n-1)){
        xx[++ans]=(n-1)*num;    
    }    
    for(int i=step;prime[i]*prime[i]<=n;i++){
        int t=prime[i];
        for(int j=prime[i]+1;j<=n;t*=prime[i],j+=t){
            if(n%j==0) dfs(i+1,n/j,num*t);
        }
    }
}
int main(){
    euler();
    while(scanf("%d",&n)!=EOF){
        ans=0;
        dfs(1,n,1);
        sort(xx+1,xx+1+ans);
        printf("%d\n",ans);
        for(int i=1;i<=ans;i++){
            printf("%lld ",xx[i]);
        }
        if(ans) puts("");
    }
    return 0;
}