1629：聪明的燕姿

题目描述

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

可是燕姿不一样，燕姿知道自己等的人是谁，因为燕姿数学学得好！燕姿发现了一个神奇的算法：假设自己的号码牌上写着数字 $S$，那么自己等的人手上的号码牌数字的所有正约数之和必定等于 $S$。

所以燕姿总是拿着号码牌在地铁和人海找数字（喂！这样真的靠谱吗）可是她忙着唱《绿光》，想拜托你写一个程序能够快速地找到所有自己等的人。

输入格式

输入包含 $k$ 组数据。

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

输出格式

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

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

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

样例

样例输入 #1

42

样例输出 #1

3
20 26 41

样例解释 #1

• 输入 $S=42$。
• 寻找所有正整数 $n$，使得 $n$ 的所有正约数之和等于 $42$。
• 满足条件的 $n$ 有 $20, 26, 41$：
  • $20$ 的约数：$1,2,4,5,10,20$，和 $1+2+4+5+10+20=42$。
  • $26$ 的约数：$1,2,13,26$，和 $1+2+13+26=42$。
  • $41$ 的约数：$1,41$，和 $1+41=42$。
• 输出 $m=3$，然后升序输出 $20,26,41$。

数据范围

对于 $100\%$ 的数据，$k \le 100$，$S \le 2 \times 10^9$。

时空限制

• 时间限制：1000 ms
• 内存限制：524288 KB

注意：本题是已知约数和 $S$，求所有满足条件的数 $n$。设 $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$，则其约数和 $\sigma(n) = \prod_{i=1}^k (1 + p_i + p_i^2 + \cdots + p_i^{a_i}) = \prod_{i=1}^k \frac{p_i^{a_i+1} - 1}{p_i - 1}$。

问题转化为：将 $S$ 分解成若干个因子 $\frac{p^{a+1} - 1}{p - 1}$ 的乘积，其中 $p$ 是质数，$a \ge 1$。我们需要搜索所有可能的分解方式，然后计算出对应的 $n$。

由于 $S \le 2 \times 10^9$，$\sqrt{S} \le 44721$，我们可以预处理所有小于等于 $\sqrt{S}$ 的质数（实际上需要更大一些，因为 $p$ 可能大于 $\sqrt{S}$，但此时 $a=1$，因子为 $1+p$）。搜索时，从最小的质数开始枚举，尝试将 $S$ 除以 $\frac{p^{a+1} - 1}{p - 1}$（其中 $a$ 从 $1$ 开始递增，直到该值大于 $S$），递归搜索。注意剪枝：如果当前剩余的 $S$ 减 $1$ 后是质数且大于当前质数，则得到一种解（因为 $1+p$ 形式）。

具体步骤：

1. 预处理质数表（至少到 $50000$）。
2. DFS 搜索，参数：当前剩余值 $res$，当前最小质数下标 $start$，当前累积值 $cur$。
3. 如果 $res = 1$，则找到一个解 $cur$，加入答案集合。
4. 否则，从 $start$ 开始枚举质数 $p$，对于每个 $p$，枚举指数 $a$ 从 $1$ 开始，计算 $t = 1 + p + p^2 + \cdots + p^a$，如果 $t > res$ 则 break。如果 $res \bmod t == 0$，则递归搜索 $res/t$，$cur \times p^a$，下一个质数从 $p$ 的下一个开始（因为质数递增，避免重复）。
5. 此外，如果 $res-1$ 是质数且 $res-1 \ge p$（避免重复），则得到解 $cur \times (res-1)$（因为 $1 + (res-1) = res$，对应 $a=1$）。
6. 注意 $cur$ 和 $p^a$ 可能超过 long long 范围，需要判断溢出。

最后，将答案排序输出。注意 $S=1$ 时，$n=1$ 的约数和为 $1$，但 $n=1$ 可能不是“号码牌”？题目要求“号码牌数字”，应该可以是 $1$ 吧？但样例中 $S=42$ 没有 $1$，因为 $1$ 的约数和为 $1$。需要看题目是否允许 $n=1$。通常 $1$ 的约数和是 $1$，如果 $S=1$ 则 $n=1$ 是一个解。但题目中 $S \ge 2$？没有明确，但 $k \le 100$，$S$ 可能为 $1$。需要处理。

由于 $k \le 100$，$S$ 最大 $2\times 10^9$，搜索不会太深。注意去重和排序。