题目分析

给定数字 $S$，需要找到所有数字 $x$，使得 $x$ 的所有正约数之和等于 $S$。即：

$$\sigma(x) = \sum_{d|x} d = S$$

这是一个经典的逆约数和问题，在数论中称为 "inverse divisor sum" 问题。

解题思路

核心思想

利用约数和函数的乘性性质，通过DFS搜索所有可能的质因数分解组合：

如果 $x = p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$，那么：

$$\sigma(x) = \prod_{i=1}^k (1 + p_i + p_i^2 + \cdots + p_i^{a_i}) $$

关键技术

• 质数预处理：使用线性筛生成质数表
• DFS搜索：递归分解剩余部分，构造解
• 数学剪枝：利用质数性质减少搜索空间

算法步骤

1. 预处理质数表（线性筛法）
2. DFS搜索解空间：
   • 检查当前剩余部分是否为1（找到解）
   • 检查剩余部分-1是否为质数（特殊解）
   • 用质数的幂次继续分解
3. 排序输出结果

完整代码

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

const int MAX_N = 100000;  // 筛法范围
int n;                     // 输入的S
int ans[100005];           // 存储结果，ans[0]记录个数
int primes[50005];         // 质数表
int prime_count;           // 质数个数
bool is_composite[MAX_N + 5];  // 标记是否为合数

// 线性筛法预处理质数
void sieve() {
    is_composite[1] = true;
    
    for (int i = 2; i <= MAX_N; i++) {
        if (!is_composite[i]) {
            primes[++prime_count] = i;
        }
        
        for (int j = 1; j <= prime_count && 1LL * primes[j] * i <= MAX_N; j++) {
            is_composite[primes[j] * i] = true;
            
            if (i % primes[j] == 0) {
                break;
            }
        }
    }
}

// 检查一个数是否为质数
bool is_prime(long long x) {
    if (x == 1) return false;
    if (x == 2) return true;
    if (x % 2 == 0) return false;
    
    for (long long i = 3; i * i <= x; i += 2) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

// DFS搜索所有解
// now: 剩余需要分解的部分
// prime_idx: 当前考虑的质数索引
// current_product: 已构建的数字
void dfs(int now, int prime_idx, long long current_product) {
    // 情况1：剩余部分为1，找到完整解
    if (now == 1) {
        ans[++ans[0]] = current_product;
        return;
    }
    
    // 情况2：剩余部分-1是质数，且大于当前质数
    // 这对应形如 x = p^(a) * q 的情况，其中q = now-1是质数
    if (is_prime(now - 1) && (now - 1) >= primes[prime_idx]) {
        ans[++ans[0]] = current_product * (now - 1);
    }
    
    // 情况3：用质数的幂次继续分解剩余部分
    for (int i = prime_idx; i <= prime_count; i++) {
        int p = primes[i];
        
        // 剪枝：如果p^2 > now，说明无法继续分解
        if (1LL * p * p > now) {
            break;
        }
        
        // 计算质数p的幂次对应的约数和部分
        long long power_sum = 1 + p;  // 1 + p
        long long power = p;          // p^1
        
        // 尝试p的各个幂次
        while (power_sum <= now) {
            // 如果当前幂次的约数和能整除剩余部分
            if (now % power_sum == 0) {
                // 递归分解剩余部分
                dfs(now / power_sum, i + 1, current_product * power);
            }
            
            // 计算下一个幂次
            power *= p;
            power_sum += power;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    // 预处理质数表
    sieve();
    
    // 处理多组数据
    while (cin >> n) {
        // 重置结果计数器
        ans[0] = 0;
        
        // 搜索所有解
        dfs(n, 1, 1);
        
        // 输出结果
        if (ans[0] == 0) {
            cout << "0\n";
        } else {
            // 排序结果
            sort(ans + 1, ans + ans[0] + 1);
            
            // 输出个数
            cout << ans[0] << '\n';
            
            // 输出所有解
            for (int i = 1; i <= ans[0]; i++) {
                cout << ans[i];
                if (i < ans[0]) cout << ' ';
            }
            cout << '\n';
        }
    }
    
    return 0;
}

代码说明

关键数据结构

• primes[]：预处理得到的质数表
• ans[]：存储所有解，ans[0]记录解的个数
• is_composite[]：标记数组，用于筛法

算法核心

1. 质数预处理（线性筛）

void sieve() {
    // 标准的线性筛算法
    // 时间复杂度 O(n)，空间复杂度 O(n)
}

2. DFS搜索逻辑

三种情况处理：

1. 完整解：

   if (now == 1) {
       ans[++ans[0]] = current_product;
       return;
   }
   

   当剩余部分完全分解时，当前构造的数字就是一个解。

2. 特殊解：

   if (is_prime(now - 1) && (now - 1) >= primes[prime_idx]) {
       ans[++ans[0]] = current_product * (now - 1);
   }
   

   对应形如 $x = \text{current\_product} \times (\text{now}-1)$ 的情况，其中 $\text{now}-1$ 是质数。

3. 继续分解：

   for (int i = prime_idx; i <= prime_count; i++) {
       // 尝试用质数p的各个幂次分解剩余部分
   }
   

   对于每个质数 $p$，尝试所有可能的幂次 $p^k$，计算对应的约数和 $1 + p + p^2 + \cdots + p^k$。

3. 数学剪枝

• 质数平方剪枝：if (1LL * p * p > now) break;
• 单调性剪枝：质数按递增顺序使用，避免重复

数学原理

约数和函数的性质：

• 如果 $\gcd(a,b) = 1$，则 $\sigma(ab) = \sigma(a)\sigma(b)$
• 对于质数幂 $p^k$，$\sigma(p^k) = 1 + p + p^2 + \cdots + p^k = \frac{p^{k+1}-1}{p-1}$

算法正确性： 通过DFS枚举所有可能的质因数分解组合，确保找到所有满足 $\sigma(x) = S$ 的数字 $x$。

复杂度分析

• 预处理：$O(\text{MAX\_N})$ 线性筛
• DFS搜索：最坏 $O(\sqrt{S} \cdot d(S))$，其中 $d(S)$ 是 $S$ 的约数个数
• 空间复杂度：$O(\text{MAX\_N})$

由于 $S \leq 2 \times 10^9$ 且解的数量很少，该算法在实践中有很好的性能。