手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

全球百事通！聪明的燕姿

2023-03-11 15:55:47 来源：博客园

聪明的燕姿

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

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

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

【资料图】

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

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

输入格式

输入包含 $k$ 组数据。

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

输出格式

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

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

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

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

数据范围

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

输入样例：

输出样例：

320 26 41

解题思路

最近又重新做了下这道题，顺便看了下以前写的题解发现很多东西写得莫名奇妙的（）

因此打算重新写过一篇，以前的题解就不删了，可以点击这里的链接查看：聪明的燕姿。

写完后发现还是很长，看不下去可以关掉，毕竟不敢对题解的质量进行保证qwq。

首先看到约数之和就很容易想到公式

$$\prod\limits_{i=1}^{n}{\sum\limits_{j=0}^{\alpha_i}{P_i^j}} = \left( {P_1^0 + P_1^1 + \cdots + P_1^{\alpha_1}} \right) \cdot \left( {P_2^0 + P_2^1 + \cdots + P_2^{\alpha_2}} \right) \cdots \left( {P_n^0 + P_n^1 + \cdots + P_n^{\alpha_n}} \right)$$

因此问题就变成了有多少个质因子 $P_i$ 以及对应的次幂 $\alpha_i$ 所构成的项 $\sum\limits_{j=0}^{\alpha_i}{P_i^j}$ 累乘得到的结果恰好为 $S$。

看上去似乎没有很好的解决方法，那只能通过枚举所有的 $P_i$ 和 $\alpha_i$ 来统计了。我们来分析一下暴搜的可行性，首先最多会有多少项进行累乘呢？通过放缩容易发现

$$\begin{align*} 2 \times {10}^{9} &= \left( {1 + P_{1} + \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) \\ &= 836075520 \end{align*}$$

因此递归的深度不会超过 $10$ 层。所以在每一层中，我们可以从小到大来枚举质数 $P_i$，同时对于每个 $P_i$ 也从小到大枚举对应的次幂 $\alpha_i$。为了防止重复搜索，当递归到下一场时我们规定必须从大于 $P_i$ 的质数开始枚举，这样就能保证在得到的约数和中，有 $P_1 < P_2 < \cdots < P_n$。

那么质数 $P_i$ 最大可以枚举到多少呢？首先很容易知道 $P_i$ 一定小于 $S$，因为 $1$ 和 $S$ 本身就是 $S$ 的两个约数，而 $1+S$ 就超过 $S$ 了，因此一定有 $P_i < S$。所以按照上面的做法的，每一层枚举的质数都小于 $S$，由于最多要递归 $9$ 层来枚举，因此即使不考虑枚举 $\alpha_i$，仅是枚举质数的计算量就达到 $\pi^9(S)$ 的级别（其中 $\pi(x)$ 表示不超过 $x$ 的质数的个数）。我们继续看一下还有什么性质。

假设在约数之和的公式中存在某个质因子满足 $P_i \geq \sqrt{S}$，那么该质因子对应的次幂 $\alpha_i$ 一定恰好为 $1$，即对应的项一定是 $1 + P_i^1$ 这个形式，而不可能是 $1 + P_i^1 + P_i^2 + \cdots$ 这个形式。因为即使考虑 $1 + P_i^1 + P_i^2$ 就已经有 $1 + P_i^1 + P_i^2 \geq 1 + \sqrt{S} + S > S$，此时约数之和就必定超过 $S$ 了。

同时还可以发现如果存在某个质因子满足 $P_i \geq \sqrt{S}$，那么该质因子就只能恰好是 $P_n$ 这个最大的质因子。反证法，否则至少存在两个质因子满足 $P_j > P_i \geq \sqrt{S}$，根据上面的结论必然有 $\alpha_i = \alpha_j = \cdots = \alpha_n = 1$，此时的约数之和为

$$\begin{align*}\prod\limits_{i=1}^{n}{\sum\limits_{j=0}^{\alpha_i}{P_i^j}} &= \left( {P_1^0 + P_1^1 + \cdots + P_1^{\alpha_1}} \right) \cdot \left( {P_2^0 + P_2^1 + \cdots + P_2^{\alpha_2}} \right) \cdots \left( {P_i^0 + P_i^1} \right) \cdot \left( {P_j^0 + P_j^1} \right) \cdots \left( {P_n^0 + P_n^1} \right) \\ &> \left( {P_i^0 + P_i^1} \right) \cdot \left( {P_j^0 + P_j^1} \right) \\ &> 1 + P_i + P_j + P_i \cdot P_j \\ &> P_i \cdot P_j \\ &\geq S\end{align*}$$

这就与约数之和为 $S$ 矛盾了。

综合上面的结论，我们得到在约数之和的公式中，最多只会存在一个质因子 $ P_n \geq\sqrt{S}$ （即最大的那个质因子），且对应的次幂一定是 $\alpha_n = 1$。

当 $P_n < \sqrt{S}$，那么 $S = \prod\limits_{i=1}^{n}{\sum\limits_{j=0}^{\alpha_i}{P_i^j}}$。

当 $P_n \geq \sqrt{S}$，有以下两种情况：

$S = \prod\limits_{i=1}^{n}{\sum\limits_{j=0}^{\alpha_i}{P_i^j}} \ , \ \ n > 1$
$S = 1 + P_1 \ , \ \ n = 1$

因此当我们枚举质因子 $P_i$ 时只需要枚举到 $\sqrt{S}$ 就可以了，超过 $\sqrt{S}$ 的质因子 $P_n$ 直接进行特判。假设之前枚举的 $n-1$ 个质数得到的累乘结果记为 $\prod\limits_{i=1}^{n-1}{\sum\limits_{j=0}^{\alpha_i}{P_i^j}} = \text{prod}$，由于 $P_n$ 必然是公式中最大的那个质因子，因此如果要满足 $\text{prod} \cdot (1 + P_n) = S$，那么一定有 $P_n = \dfrac{S}{\text{prod}} -1$，同时 $P_n$ 是质数且 $P_n > P_{n-1}, \ P_n \geq \sqrt{S}$。

先给出这种搜索顺序的代码（其实这个搜索代码还是会 TLE）：

1 void dfs(int cur, int prod, int num) { 2     if (prod == s) { 3         ans[sz++] = num; 4         return; 5     } 6     int r = s / prod; 7     if (is_prime(r - 1) && r - 1 >= primes[cur] && (r - 1) >= s / (r - 1)) ans[sz++] = num * (r - 1); 8     for (int i = cur; primes[i] <= s / primes[i]; i++) { 9         for (int j = 1 + primes[i], k = primes[i]; j <= s; k *= primes[i], j += k) {10             if (r % j == 0) dfs(i + 1, prod * j, num * k);11         }12     }13 }

先解释以下各个参数的含义，首先 $\text{cur}$ 表示当前从第 $\text{cur}$ 个质数开始枚举。$\text{prod}$ 的定义与上面相同，即之前枚举质数的各项累乘。$\text{num}$ 表示约数之和为 $\text{prod}$ 所对应的那个数，即 $\text{num}$ 的约数之和等于 $\text{prod}$。

很明显当 $\text{prod} = S$，那么此时 $\text{num}$ 就是我们要找的数。

否则我们先判断是否存在质因子 $P_n \geq \sqrt{S}$ 使得 $\text{prod} \cdot (r - 1) = S$，在代码中 $P_n = \dfrac{S}{\text{prod}} -1 = r-1$。如果满足 $r-1$ 是质数，且 $r-1 \geq \text{primes}[\text{cur}], \ r - 1 \geq \sqrt{S}$，那么 $\text{prod} \cdot (r - 1)$ 就是我们要找的答案。

然后再去枚举考虑不超过 $\sqrt{S}$ 的质因子，以及对应的次幂，往下一层递归。

可是这样做还是会超时的，因为计算量大概是 $\pi^9(\sqrt{S})$ 级别。继续对枚举质数的部分进行优化，可以发现在每一层中我们做的事情都是从第 $\text{cur}$ 个质数开始枚举，使得累乘的结果不超过 $r$。类比上面的分析，我们知道枚举的质数肯定要小于 $r$，并且一样可以枚举不超过 $\sqrt{r}$ 的质数，然后超过 $\sqrt{r}$ 的质因子进行特判就可以了，代码就变成下面的样子：

1 void dfs(int cur, int prod, int num) { 2     if (prod == s) { 3         ans[sz++] = num; 4         return; 5     } 6     int r = s / prod; 7     if (is_prime(r - 1) && (r - 1) >= primes[cur]) ans[sz++] = num * (r - 1); 8     for (int i = cur; primes[i] <= r / primes[i]; i++) { 9         for (int j = 1 + primes[i], k = primes[i]; j <= r; k *= primes[i], j += k) {10             if (r % j == 0) dfs(i + 1, prod * j, num * k);11         }12     }13 }

可以发现少了判断条件(r - 1) >= r / (r - 1)，这是因为 $r-1$ 一定大于 $\sqrt{r}$。这个搜索代码就可以过了。

至此搜索的部分就已经讲完了，剩下的就只需要筛出不超过 $\sqrt{2 \times 10^9}$ 的所有质数，以及写个判断是否为质数的函数就可以了。

AC代码如下：

1 #include  2 using namespace std; 3  4 const int N = 45000; 5  6 int s; 7 int primes[N], cnt; 8 bool vis[N]; 9 int ans[N], sz;10 11 void get_prime(int n) {12     for (int i = 2; i <= n; i++) {13         if (!vis[i]) primes[cnt++] = i;14         for (int j = 0; primes[j] <= n / i; j++) {15             vis[primes[j] * i] = true;16             if (i % primes[j] == 0) break;17         }18     }19 }20 21 bool is_prime(int x) {22     if (x < N) return !vis[x];23     for (int i = 0; primes[i] <= x / primes[i]; i++) {24         if (x % primes[i] == 0) return false;25     }26     return true;27 }28 29 void dfs(int cur, int prod, int num) {30     if (prod == s) {    // 搜索得到的质数和 prod 等于 s31         ans[sz++] = num;32         return;33     }34     int r = s / prod;   // 要凑的剩余部分35     if (is_prime(r - 1) && (r - 1) >= primes[cur]) ans[sz++] = num * (r - 1);   // 先考虑质因子大于 sqrt(r) 的情况36     for (int i = cur; primes[i] <= r / primes[i]; i++) {    // 再考虑质因子小于 sqrt(r) 的情况37         for (int j = 1 + primes[i], k = primes[i]; j <= r; k *= primes[i], j += k) {    // 枚举质数 i 对应的次幂38             if (r % j == 0) dfs(i + 1, prod * j, num * k);39         }40     }41 }42 43 int main() {44     get_prime(N - 1);   // 筛出不超过sqrt(2e9)的质数45     while (~scanf("%d", &s)) {46         sz = 0;47         dfs(0, 1, 1);   // 从第0个质数开始枚举搜索48         printf("%d\n", sz);49         if (sz) {50             sort(ans, ans + sz);51             for (int i = 0; i < sz; i++) {52                 printf("%d ", ans[i]);53             }54             printf("\n");55         }56     }57     58     return 0;59 }

参考资料

聪明的燕姿：https://www.cnblogs.com/onlyblues/p/15966022.html

关键词：