题解

1.由题可知我们需要求的是正约数和,由算术基本定理可知:任何一个大于1的自然数N,如果N不为质数,那么N可以唯一分解成有限个质数的乘积.显然一个数的约数也就是质数的组合,我们设自然数N由n种质数$a_i$组成,且每种质数有$b_i$个,那么因数和$s=\prod_{i=1}^n(1+a_i+…+a_i^{b_i})$
2.这样我们的基本思路就是先用欧拉筛打表求质数,然后不断求$sum_i=(1+a_1+…+a_i^{b_i})$方案(也就是使s能整除$sum_i$),并在这一过程中求得$pro=pro \times a_i^{b_i}$.但是这样有两个明显的问题:(1).我们没有足够的空间存储$2^{31}$也就是2.1e9这个级别的int($2.1e9*4/1024/1024\approx8010M$);(2)我们很难直接对a_i和b_i分别枚举来获得结果且大概率超时(如果大哥有请留言,暂时还没思路),因此我们可以考虑dfs搜索符合要求的解,但是即使这样在每重递归中直接套两层递循环也是难以想象的——我们还需要进行适当地剪枝
3.对于上面两个问题的办法就是在枚举过程中最后一层进行特殊处理,设$sum_i=(1+a_1+…+a_i^{b_i})$,$s=s/sum_i$,pro表示当前获得的解,我们分为三种情况讨论:(1).s=1,显然此时将pro收入ans数组即可;(2).$s=(1+a_n)$,这里只要直接判断s-1是不是素数即可,如果是素数就直接收入ans数组.此外,我们还能注意到$(1+a_{n-1})(1+a_n)<=s即a_i<\sqrt{s}$,这样我们只要求50000以内的素数即可.而在枚举时我们必然是以一个特定的顺序进行枚举,避免重复或是缺漏,如果从小到大对质数枚举时,在确定(s-1)不是最终解后,以last表示上一个被枚举的的质数,必然只有$a_{last}^2>s(因为s>=(1+a_{last+1}+a_{last+1}^2)$可能有解,这样就做到了剪枝;(3).$s=(1+a_i+…+a_i^{b_i})$,此时可以转换到第(1)种情况下求解,但是同样有着$s>a_i^2的特征$

时间复杂度

显然这道题的空间复杂度不难算,比较麻烦的是时间复杂度的求解,关于搜索的时间复杂度求解个人认为是真的比较大的一个难点.
(1).循环
50000以内共5133个素数,primes分布:
primes<=10:4;primes<=100:20;primes<=1000:142;primes<=10000:1060;primes<=3903;
由于循环界限是$primes^b<=s$,$4\times30+20\times10+142\times5+1060\times3+3903\times2=12016$
(2).递归层数——最多所含的质因子种数
$s=(1+a_1…+a_1^{b_1})…(1+a_n…+a_n^{b_n})$,
s>=(1+1)(1+2)(1+3)(1+5)(1+7)(1+11)(1+13)(1+15)(1+17)(1+19)(1+23)=$2.5e^{10}$,大概是10这个数量级
(3).100组数据
综上:$100\times12016\times10=1.2\times10^7$(很抱歉,由于个人能力所限,以上只是一个粗略的估计,希望能有大神来指出错误)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=5e4+10;

int primes[N],cnt,ans[N],num;
bool st[N];

void get_primes()
{
    for(int i=2;i<=N;i++){
        if(!st[i]) primes[++cnt]=i;
        for(int j=1;i*primes[j]<=N;j++){
            st[i*primes[j]]=true;
            if(i%primes[j]==0) break;
        }
    }
}

bool check(int x)
{
    if(!x) return true;
    for(int i=1;primes[i]<=x/primes[i];i++){
        //放置相乘越界
        if(x%primes[i]==0) return false;
    }
    return true;
}

void dfs(int last,int s,int pro)
{
    if(s==1){ //递归出口1
        ans[++num]=pro;
        return ;
    }
    else if(check(s-1)&&(s-1)>primes[last]){ //递归出口2,这边primes[last]肯定不能再过了,因为有1做限制
        ans[++num]=pro*(s-1);
    }
    for(int i=last+1;primes[i]<=s/primes[i];i++){
        //剪枝
        for(int j=primes[i],sum=1+j;sum<=s;j*=primes[i],sum+=j){
            //防止重复第二个递归出口
            if(s%sum==0&&!(sum==1+primes[i]&&s==sum)) dfs(i,s/sum,pro*j);
        }
    }
}

int main()
{
    int s;
    cnt=0;
    get_primes();
    primes[0]=0;
    while(cin >> s){
        num=0; //多组输入注意重置
        dfs(0,s,1); //last,s,pro
        sort(ans+1,ans+1+num);
        cout << num << endl;
        if(num){
            bool sign=1;
            for(int i=1;i<=num;i++){
                if(sign){
                    cout << ans[i];
                    sign=0;
                }
                else{
                    cout << ' ' << ans[i];
                }
            }
            cout << endl;
        }
    }
    return 0;
}