写了大半天的题解，大体上是从y总的思路一步一步开始引导思考的一个具体的过程总结

同时我还总结了我觉得y总讲的时候代码里面没说清楚的部分的理解，有不妥的地方欢迎及时给我指出来！！！，跪求点赞支持qwqwq呜呜呜

题意

题目的大意就是给一个数S

让你找到有多少数能够满足它约数的和等于S

比如S = 42

这个时候就有3个数满足条件

41 = (1 + 41) == 42
20 = (1 + 2 + 4 + 5 + 10 + 20) == 42
26 = (1 + 2 + 13 + 26) == 42

分析思路

算术基本定理

N = P1^a1 * P2^a2 * … * Pn^an
则N的约数个数为(a1+1)(a2+1)…(an+1)

假设N的一个约数为D

D = P1^b1 * P2^b2 * … * Pn^bn
其中bi可以取到0，范围是0<= bi <= ai

因为只有和N的质因数一一对应一定能得到约数
因为bi可以从0取到ai,那么每一个bi就有(ai+1)种选法

约数的个数就是每个bi对应多少种选法相乘
即约数个数就为(a1+1)(a2+1)…(an+1)

约数之和S = (1+p1+p1^2+…+p1^a1)(1+p2+p2^2+…+p2^a2)…(1+pn+pn^2+…+pn^an)

这个怎么理解呢

因为每一个约数为D = P1^b1 * P2^b2 * … * Pn^bn

那么S = (1+p1+p1^2+…+p1^a1)(1+p2+p2^2+…+p2^a2)…(1+pn+pn^2+…+pn^an)

这个公式的意思就是从每个括号里面取出来一个数然后相乘，就能得到一个约数Di
然后所有的约数Di相加就得到约数之和S

举个例子

对于S = 42来说，42对应的结果里面有一个为20，20 = (1 + 2 + 4 + 5 + 10 + 20)
20 = 2^2*5
对于两个质因数2和5来说
2可以取0,1,2次，5可以取0,1次
所以S = (1+2+2^2)(1+5) = 42

继续分析

所以我们最暴力的想法一定就是枚举了，比如对一个数S
枚举从1到S-1的所有数的约数，再判断他们的约数和是否等于S

但是这么做显然会超时，因为1 <= S <= 2*10^9

这个时候我们就可以观察我们的约数和的公式
S = (1+p1+p1^2+…+p1^a1)(1+p2+p2^2+…+p2^a2)…(1+pn+pn^2+…+pn^an)

假设这个时候有一个约数和S满足(1+2)(1+2+2^2)(1+2+2^2+…+2^k)
3x5x9x17x33x65x129 = 635037975 就已经接近1e9的量级了，可见符合条件的项不会很多

那么这个时候我们就可以用dfs进行搜索，看我们能不能得到符合条件的(1+pk+pk^2+…+pk^ak)能够使得
S能够整除，即S % (1+pk+pk^2+…+pk^ak) == 0
然后S /= (1+pk+pk^2+…+pk^ak),再dfs到下一层

应该先从小到大枚举P

for(p : 2,3,5,7,...)
    for(a : 1,2,3,...)
        if(S mod (1+p1+p1^2+...+p1^a1) == 0)
            dfs(下一层)

这个时候我们还需要继续思考特殊情况

如果ai = 1的话，S = (1+Pi)的时候，因为Pi为质数，那么S-1也一定为质数，那么这个时候只需要判断S-1是否为质数即可

又S只会有两种情况，就是一种情况包括一个因子里面有(1+Pi)，另一种情况不包括(1+Pi)
S = (1+Pi)(1+Pj+Pj^2.....)
S = (1+Pi+Pi^2)(1+.....)

但是这两种情况都可以看出来Pi ^2 <= S
所以我们dfs枚举Pi的上限就是$\sqrt{ S }$

所以dfs应该设置成三个参数dfs(last,product,S)

1.last参数

表示上一个枚举的质数是谁，我们这样枚举的目的就是先把前面符合条件的质数枚举完了再枚举后面的质数，这样不会带来重复，降低了时间复杂度

比如质数为P = 2,3,5,7....

如果枚举2之后再dfs到下一层，那么这个时候就应该再从3开始进行枚举而不是再从头开始枚举

2.product参数

product表示 S = (1+p1+p1^2+…+p1^a1)(1+p2+p2^2+…+p2^a2)…(1+pn+pn^2+…+pn^an)中

当前进行到哪一个括号里面的最高次项Pi^ai的乘积和
比如S = (1+2+2^2)(1+3+3^2+3^3)(1+....)
则dfs到第三层的时候product = 2^2*3^3 (product : 1 – > 2^2 – > 2^2*3^3)

又由算术基本定理可知
一个数N = P1^a1 * P2^a2 * … * Pn^an

product = P1^a1 * P2^a2*.....

如果product要从第一层(一开始product初始化为1)进到第二层，此时product(2) = product(1) * P1^a1
S = S’ / (1+p1+p1^2+…+p1^a1)

然后再dfs(last,product(2),S) ==(等价于) dfs(last , product(1)*P1^a1 , S’/(1+p1+p1^2+…+p1^a1))

3.S参数

从上面的分析可知S参数就代表着从一开始的S除以(1+pk+pk^2+…+pk^ak)后剩余的乘积

所以每一层我们都应当判断S-1是否为质数，如果S-1是质数的话,也需要记录，但是不需要返回上一层继续往下搜即可
就比如24
24 = (1+23)
= (1+2)(1+7)
= (1+3)(1+5)
第一层的时候判断23是质数，所以记录res[len++] = 1*23
同时也需要继续往下做然后依次判断2、7 或者3、5能不能满足条件
只要有S-1为质数，说明就有满足条件的数，这个时候就需要记录结果

为什么S-1一定要大于上一层的质数？

因为我们要保证质数是从小到大枚举的，只有剩下的S-1是大于上一层的质数的时候，(1+S)才有可能成为最初的那个S的一个因子

因为我们要表示S’ = (1+ 2 + 2^2+…)(1 + 3 + 3^2 + …)…(1+S)
越往后枚举对应的那个Pi也越大，所以S-1一定要大于上一层的质数才能满足条件

S == 1对应的是什么情况？

S == 1对应的就是S’只由一个括号即只有一个P,S’ = (1+p+p^2+…+p^k)组成的情况
比如 7 = (1 + 2 + 2^2) ----->对应4
13 = (1 + 3 + 3^2) ----->对应9
15 = (1 + 2 + 2^2 + 2^3) ----->对应8
这种情况表明，我从p = primes[i]开始枚举，一个p得到的序列和就把一开始的S’给整除了或者说这个序列和与S’相等，即此时的p得到的序列和(1+p+p^2+…+p^k) == S’

所以此时S’ / (1+p+p^2+…) == 1
dfs到下一层直接就是dfs(last,p^k,1)
那么dfs到下一层S == 1的时候,product = p^k就是对应我们要找的那个数

注意点

1.求质数的过程应该用线性筛的方法去做
2.dfs(last,product,S)其中last应该初始化为-1
这样我们在一开始判断S-1大于前面的质数的时候应该特判,S-1 > ((last < 0) ? 0 : primes[last])
因为最小是(1+2)那么S起码是2,所以应该有S > 1 即S-1 > 0

代码如下

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 50000;//N = sqrt(2e9)
bool st[N];
int primes[N],cnt = 0;//线性筛
int S,res[N],len;

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

int is_prime(int n)
{
    if(n < N) return !st[n];//没有被筛过说明就是质数，返回true
    for(int i = 0;primes[i] <= n / primes[i];i++)
    {
        if(n % primes[i] == 0) return false;
    }
    return true;
}

void dfs(int last,int product,int S)//last表示上一个用的质数的下标是什么,product当前最高次项的结果,S表示每次处理后剩余多少
{
    if(S == 1)
    {
        res[len++] = product;
        return ;
    }
    //比如20 = 2^2 * 5
    //N = P1^a1 * P2^a2 * ... * Pn^an
    //S = (1+p1+p1^2+...+p1^a1)(1+p2+p2^2+...+p2^a2)...(1+pn+pn^2+...+pn^an)
    //42 = (1 + 2 + 2^2)*(1 + 5),其中2^2和5就分别是最高次项p1^2*p2^1
    if(S-1 > ((last < 0) ? 0 : primes[last]) && is_prime(S-1))
    {
        res[len++] = product * (S-1);
    }
    for(int i = last+1;primes[i] <= S / primes[i];i++)
    {
        int p = primes[i];
        for(int j = 1+p,t = p;j <= S;t *= p,j += t)
        {
            if(S % j == 0)
            {
                dfs(i,product*t,S/j);
            }
        }
    }
}

int main()
{
    get_primes(N-1);
    while(cin>>S)
    {
        len = 0;
        dfs(-1,1,S);

        sort(res,res+len);

        cout << len << endl;
        if (len)
        {
            sort(res, res + len);
            for (int i = 0; i < len; i ++ ) cout << res[i] << ' ';
            cout << endl;
        }
    }
    return 0;
}