聪明的燕姿

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

可是燕姿不一样，燕姿知道自己等的人是谁，因为燕姿数学学得好！

燕姿发现了一个神奇的算法：假设自己的号码牌上写着数字 $S$，那么自己等的人手上的号码牌数字的所有正约数之和必定等于 $S$。

所以燕姿总是拿着号码牌在地铁和人海找数字（喂！这样真的靠谱吗）。

可是她忙着唱《绿光》，想拜托你写一个程序能够快速地找到所有自己等的人。

输入格式

输入包含 $k$ 组数据。

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

输出格式

对于每组数据，输出有两行。

第一行包含一个整数 $m$，表示有 $m$ 个等的人。

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

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

数据范围

$1 \leq k \leq 100$,
$1 \leq S \leq 2 \times {10}^{9}$

输入样例：

42

输出样例：

3
20 26 41

解题思路

　　昨天被这道题卡了一天，很多的地方都理解不了。

　　另外，题目描述的明明是《遇见》好吧。建议改为“懒 惰 的 燕 姿”，不出专辑就算了，还要我帮她做数论题，关键是我还不会做。[doge]

　　题目就是问有多少个数的约数和恰好等于$s$。

　　根据唯一分解定理，一个数可以唯一分解成若干个素数的乘积形式，$N = P_{1}^{\alpha_{1}} \cdot P_{2}^{\alpha_{2}} \cdot \cdots \cdot P_{n}^{\alpha_{n}}$，其中$P_{i}$为素数，且$\alpha_{i} > 0, P_{1} < P_{2} < \cdots < P_{n}$。

　　首先一个数所有约数的个数公式：$\left( {\alpha_{1} + 1} \right) \cdot \left( {\alpha_{2} + 1} \right) \cdot \cdots \cdot \left( {\alpha_{n} + 1} \right)$。

　　一个数所有约数的和公式：$\left( {1 + P_{1} + P_{1}^{2} + \cdots + P_{1}^{\alpha_{1}}} \right) \cdot \left( {1 + P_{2} + \cdots + P_{2}^{\alpha_{2}}} \right) \cdot \cdots \cdot \left( {1 + P_{n} + \cdots + P_{n}^{\alpha_{n}}} \right)$。

　　首先可以发现我们要找的数一定是小于$s$的，如果有$x \geq s$，因为$1$和$x$都是$x$的约数，因此仅看这两个约数的和$x + 1$已经大于$s$了，因此要找的数一定小于$s$。

　　因此我们要的数的约数和应该满足这种形式：$$s = \left( {1 + P_{1} + P_{1}^{2} + \cdots + P_{1}^{\alpha_{1}}} \right) \cdot \left( {1 + P_{2} + \cdots + P_{2}^{\alpha_{2}}} \right) \cdot \cdots \cdot \left( {1 + P_{n} + \cdots + P_{n}^{\alpha_{n}}} \right)$$

　　然后我们看看约数和公式的每一项$\left( {1 + P_{i} + \cdots + P_{i}^{\alpha_{i}}} \right)$，粗略估计一下一共有多少项$\left( {1 + P_{i} + \cdots + P_{i}^{\alpha_{i}}} \right)$。

$$\begin{align*} 2 \times {10}^{9} &= \left( {1 + P_{1} + P_{1}^{2} + \cdots + P_{1}^{\alpha_{1}}} \right) \cdot \left( {1 + P_{2} + \cdots + P_{2}^{\alpha_{2}}} \right) \cdot \cdots \cdot \left( {1 + P_{n} + \cdots + P_{n}^{\alpha_{n}}} \right) \\ &> \left( {1 + 2} \right) \cdot \left( {1 + 3} \right) \cdot \left( {1 + 5} \right) \cdot \left( {1 + 7} \right) \cdot \left( {1 + 11} \right) \cdot \left( {1 + 13} \right) \cdot \left( {1 + 17} \right)  \cdot \left( {1 + 19} \right) \cdot \left( {1 + 23} \right) \end{align*} $$

　　可以发现通过粗略的估计，当枚举到素数$23$时还是小于$2 \times {10}^{9}$的，当枚举到素数$29$时已经大于$2 \times {10}^{9}$了，因此可以发现$\left( {1 + P_{i} + \cdots + P_{i}^{\alpha_{i}}} \right)$一共不会超过$10$项，所以可以用dfs来爆搜每一个$P_{i}$和$\alpha_{i}$，递归的深度不会超过$10$。

　　另外一个问题是，如果我们在每一层枚举$P_{i}$时直接从$2$枚举到$s$，时间复杂度就很高了，因此需要剪支。

　　可以证明对于等式$s = \left( {1 + P_{1} + P_{1}^{2} + \cdots + P_{1}^{\alpha_{1}}} \right) \cdot \left( {1 + P_{2} + \cdots + P_{2}^{\alpha_{2}}} \right) \cdot \cdots \cdot \left( {1 + P_{n} + \cdots + P_{n}^{\alpha_{n}}} \right)$，如果存在一个$P_{i} \geq \sqrt{s}$，那么一定只会是$s = 1 + P_{i}$这个形式。

　　反证法，假设存在至少两个$P_{i} \geq \sqrt{s}, P_{j} \geq \sqrt{s}$，且$P_{i} < P_{j}$（因为我们规定在素数分解中，前一个素数要小于后一个素数），满足$s = \left( {1 + P_{1} + P_{1}^{2} + \cdots + P_{1}^{\alpha_{1}}} \right) \cdot \cdots \cdot \left( {1 + P_{i} + \cdots + P_{i}^{\alpha_{1}}} \right) \cdot \left( {1 + P_{j} + \cdots + P_{j}^{\alpha_{2}}} \right) \cdot \cdots \cdot \left( {1 + P_{n} + \cdots + P_{n}^{\alpha_{n}}} \right)$，我们先只取出其中两项来看，$\left( {1 + P_{i} + \cdots + P_{i}^{\alpha_{1}}} \right) \cdot \left( {1 + P_{j} + \cdots + P_{j}^{\alpha_{2}}} \right)$，继续缩小成$\left( {1 + P_{i}} \right) \cdot \left( {1 + P_{j}} \right) = 1 + P_{i} + P_{j} + P_{i} \times P_{j} > P_{i} \times P_{j} > \sqrt{s} \times \sqrt{s} = s$，就与$\leq s$这个条件矛盾了，因此如果存在一个$P_{i} \leq \sqrt{s}$，那么一定只会有$s = 1 + P_{i}$这个形式。

　　再证明唯一性。假设存在两个$P_{i} \geq \sqrt{s}, P_{j} \geq \sqrt{s}$，且$P_{i} < P_{j}$，根据上面的证明，一定会有$s = 1 + P_{i}, s = 1 + P_{j}$。因为$s = s$，所以有$1 + P_{i} = 1 + P_{j}$，即$P_{i} = P_{j}$，这就与$P_{i} < P_{j}$矛盾了，因此唯一性得到证明，即如果存在一个$P_{i} \geq \sqrt{s}$且满足$s = 1 + P_{i}$，那么有且仅有$P_{i}$这一个。

　　因此结论是，如果某个数$s$的约数和中存在一个$P_{i} \geq \sqrt{s}$，那么$s$的形式一定会是$s = 1+ P_{i}$，且$\geq \sqrt{s}$的$P_{i}$有且只有这一个。

　　所以我们在搜索某一项$\left( {1 + P_{i} + \cdots + P_{i}^{\alpha_{i}}} \right)$的时候，遍历的$P_{i}$范围只需要满足$P_{i}^{2} < \sqrt{s}$就可以了，因为$\geq \sqrt{s}$的$P_{i}$最多只会有一个，且满足$s = 1 + P_{i}$这个形式，所以对于这种情况只需要进行特判一下是否满足该形式就可以了。

　　另外一些细节会在注释中补充，AC代码如下：

 1 #include 
 2 #include 
 3 #include 
 4 using namespace std;
 5 
 6 const int N = 1e5 + 10;
 7 
 8 int primes[N], cnt;
 9 bool vis[N];
10 vector<int> ans;
11 
12 void get_prime(int n) {
13     for (int i = 2; i <= n; i++) {
14         if (!vis[i]) primes[cnt++] = i;
15         for (int j = 0; primes[j] <= n / i; j++) {
16             vis[primes[j] * i] = true;
17             if (i % primes[j] == 0) break;
18         }
19     }
20 }
21 
22 bool is_prime(int n) {
23     if (n < N) return !vis[n];
24     for (int i = 0; primes[i] <= n / primes[i]; i++) {
25         if (n % primes[i] == 0) return false;
26     }
27     
28     return true;
29 }
30 
31 // cur表示当前要从哪个质数的下标开始枚举，prod表示要找的答案的部分质数乘积，s表示当前要分解约数和
32 void dfs(int cur, int prod, int s) {
33     if (s == 1) {   // s == 1表示约数和已经分解完了，每一个Pi和αi已经找到
34         ans.push_back(prod);    // 答案就是各项Pi^αi的乘积
35         return;
36     }
37     
38     // 先特判一下是否存在一个Pi >= sqrt(s)，满足s == 1 + Pi -> Pi == s - 1
39     // 如果满足，等价于Pi应该大于等于当前枚举的质数，即s - 1 >= primes[cur]，且Pi要是一个质数
40     // 不return是因为Pi >= sqrt(s)只是我们枚举的一种情况而已，接下来还要枚举Pi < sqrt(s)的情况
41     if (s - 1 >= primes[cur] && is_prime(s - 1)) ans.push_back(prod * (s - 1));
42     
43     // 特判后，Pi的枚举范围就缩小到Pi^2 < s
44     for (int i = cur; primes[i] < s / primes[i]; i++) {
45         int t = primes[i];
46         // j == 1 + Pi^1 + Pi^2 + ... + Pi^αi
47         for (int j = 1 + primes[i]; j <= s; t *= primes[i], j += t) {
48             if (s % j == 0) dfs(i + 1, prod * t, s / j);    // 只有j是s的某一项，即j可以整除s，即s % j == 0才可以继续往下搜
49         }
50     }
51 }
52 
53 int main() {
54     get_prime(N - 1);   // 筛质数，我们用到的质数小于sqrt(2e9)
55     
56     int n;
57     while (~scanf("%d", &n)) {
58         ans.clear();
59         dfs(0, 1, n);
60         
61         printf("%d\n", ans.size());
62         if (!ans.empty()) {
63             sort(ans.begin(), ans.end());
64             for (auto &it : ans) {
65                 printf("%d ", it);
66             }
67             printf("\n");
68         }
69     }
70     
71     return 0;
72 }

参考资料

　　AcWing 1296. 聪明的燕姿（蓝桥杯C++ AB组辅导课）：https://www.acwing.com/video/746/