题目理解

Johnny有若干种玩具，第i种有$c_i$个。他从这些玩具中选择一些（可以选0个），使得选择的方案数正好为n。

对于第i种玩具，选择数量可以是$0,1,...,c_i$，共$c_i+1$种选法。

所以总方案数：$(c_1+1)(c_2+1)...(c_k+1) = n$

我们需要找到所有可能的玩具总数$T = c_1 + c_2 + ... + c_k$，并输出所有可能的$T$。

数学分析

我们需要将$n$分解为若干个大于等于2的正整数的乘积（因为$c_i \ge 1$，所以$c_i+1 \ge 2$）。

设$n = p_1 \times p_2 \times ... \times p_k$，其中$p_i \ge 2$。

那么$T = (p_1-1) + (p_2-1) + ... + (p_k-1) = (p_1 + p_2 + ... + p_k) - k$

所以问题转化为：

1. 将$n$分解为若干个大于等于2的整数的乘积
2. 计算$T = sum(p_i) - k$
3. 收集所有可能的$T$

解法思路

1. 因数分解：由于$n \le 10^9$，直接分解$n$的所有因数
2. 递归搜索：对于每个因数$d \ge 2$且$d \mid n$，递归分解$n/d$
3. 记忆化：使用map记录中间结果，避免重复计算
4. 去重排序：收集所有可能的$T$并排序输出

C++代码实现

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>

using namespace std;

// 记忆化搜索：返回分解n得到的所有可能总和T的集合
set<int> dfs(int n, map<int, set<int>>& memo) {
    // 如果已经计算过，直接返回
    if (memo.find(n) != memo.end()) {
        return memo[n];
    }
    
    set<int> result;
    
    // 基本情况：n=1，只有空乘积，此时k=0，sum=0，T=0-0=0
    if (n == 1) {
        result.insert(0);
        memo[n] = result;
        return result;
    }
    
    // 先把n本身作为一个因子（即只有一种玩具）
    // 此时：k=1, sum=n, T = n - 1
    result.insert(n - 1);
    
    // 寻找n的所有因子d (d >= 2且d <= sqrt(n))
    for (int d = 2; d * d <= n; d++) {
        if (n % d == 0) {
            // d是一个因子
            set<int> sub_res = dfs(n / d, memo);
            for (int t : sub_res) {
                // 当前因子d贡献：T增加d-1
                result.insert(t + d - 1);
            }
            
            // 如果d^2 != n，考虑对称的因子n/d
            if (d * d != n) {
                int d2 = n / d;
                if (d2 >= 2) {
                    set<int> sub_res2 = dfs(d, memo);
                    for (int t : sub_res2) {
                        result.insert(t + d2 - 1);
                    }
                }
            }
        }
    }
    
    memo[n] = result;
    return result;
}

int main() {
    int n;
    cin >> n;
    
    map<int, set<int>> memo;
    set<int> all_totals = dfs(n, memo);
    
    // 转换为vector并排序
    vector<int> result(all_totals.begin(), all_totals.end());
    sort(result.begin(), result.end());
    
    // 输出结果
    cout << result.size() << endl;
    for (int i = 0; i < result.size(); i++) {
        cout << result[i];
        if (i < result.size() - 1) {
            cout << " ";
        }
    }
    cout << endl;
    
    return 0;
}

优化版本（更高效）

上面的代码对于$n \le 10^9$可能有点慢，我们需要更高效的实现：

#include <bits/stdc++.h>
using namespace std;

set<int> ans;
vector<int> factors;

// 生成n的所有因子
void get_factors(int n) {
    factors.clear();
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            factors.push_back(i);
            if (i * i != n) {
                factors.push_back(n / i);
            }
        }
    }
    sort(factors.begin(), factors.end());
}

// DFS搜索所有分解方式
void dfs(int n, int sum_factors, int count_factors) {
    // 基本情况：n=1，添加当前结果
    if (n == 1) {
        ans.insert(sum_factors - count_factors);
        return;
    }
    
    // 尝试所有可能的因子d>=2
    for (int i = 1; i < factors.size(); i++) {
        int d = factors[i];
        if (d > n) break;
        if (n % d == 0) {
            dfs(n / d, sum_factors + d, count_factors + 1);
        }
    }
}

int main() {
    int n;
    cin >> n;
    
    // 特殊情况：n=1
    if (n == 1) {
        cout << 1 << endl << 0 << endl;
        return 0;
    }
    
    get_factors(n);
    ans.clear();
    
    // 从所有因子>=2开始搜索
    for (int i = 1; i < factors.size(); i++) {
        int d = factors[i];
        if (d > n) break;
        if (n % d == 0) {
            dfs(n / d, d, 1);
        }
    }
    
    // 输出结果
    vector<int> result(ans.begin(), ans.end());
    cout << result.size() << endl;
    for (int i = 0; i < result.size(); i++) {
        cout << result[i];
        if (i < result.size() - 1) cout << " ";
    }
    cout << endl;
    
    return 0;
}

算法复杂度分析

1. 时间复杂度：$O(d(n) \cdot \text{分解数})$，其中$d(n)$是n的因子个数

   • 对于$n \le 10^9$，最大因子个数约1344个
   • 实际搜索的分解数不会太多

2. 空间复杂度：$O(d(n) + \text{答案数量})$

样例验证

样例1输入：

12

输出：

4
4 5 6 11

与题目一致。

样例2输入：

36

输出：

8
6 7 8 10 11 13 18 35