【题目来源】
AtCoder：D - Cell Division
【题目描述】
Takahashi is observing a culture sample consisting of \(N\) cells.
高桥正在观察一份包含 \(N\) 个细胞的培养样本。
Each cell has an activity value represented by a positive integer. Initially, the activity value of the \(i\)-th cell is \(A_i\).
每个细胞有一个用正整数表示的活性值。初始时，第 \(i\) 个细胞的活性值为 \(A_i\)。
As long as there exists a cell with an activity value of \(2\) or more in the culture sample, Takahashi repeatedly performs the following sequence of steps as one operation:
只要培养样本中存在活性值大于等于 \(2\) 的细胞，高桥就会重复执行以下步骤序列作为一次操作：
- Choose one cell from the culture sample whose activity value is \(2\) or more. Let \(x\) be the activity value of the chosen cell.
从培养样本中选择一个活性值大于等于 \(2\) 的细胞。设所选细胞的活性值为 \(x\)。 - Choose a prime number \(p\) that divides \(x\).
选择一个能整除 \(x\) 的质数 \(p\)。 - Remove that cell from the culture sample, and add \(p\) new cells each with activity value \(x / p\) to the culture sample. (Since \(p\) is a divisor of \(x\), \(x / p\) is a positive integer.)
将该细胞从培养样本中移除，并向培养样本中添加 \(p\) 个新细胞，每个新细胞的活性值为 \(x / p\)。（由于 \(p\) 是 \(x\) 的因数，\(x / p\) 是一个正整数。）
Each operation increases the total number of cells by \(p - 1\). If the activity value of the newly added cells is \(2\) or more, they become eligible to be chosen in subsequent operations. Cells with an activity value of \(1\) cannot be chosen for operations.
每次操作会使细胞总数增加 \(p - 1\)。如果新添加的细胞的活性值大于等于 \(2\)，它们将在后续操作中可以被选择。活性值为 \(1\) 的细胞不能被选择进行操作。
In each operation, Takahashi is free to choose which cell to select and which prime number \(p\) to use. Depending on these choices, the number of operations required until all cells have an activity value of \(1\) may vary.
在每次操作中，高桥可以自由选择要操作的细胞以及使用的质数 \(p\)。根据这些选择，使得所有细胞的活性值都变为 \(1\) 所需的操作次数可能不同。
Find the minimum and maximum number of operations required to make the activity values of all cells equal to \(1\).
求使得所有细胞的活性值变为 \(1\) 所需的最小操作次数和最大操作次数。
【输入】
\(N\)
\(A_1\) \(A_2\) \(\cdots\) \(A_N\)
The first line contains an integer \(N\) representing the number of cells.
The second line contains \(N\) integers \(A_1, A_2, \ldots, A_N\) separated by spaces.
【输出】
Print the minimum and maximum number of required operations in this order, separated by a space, on a single line.
【输入样例】
3
2 3 4
【输出样例】
5 5
【核心思想】
-
问题分析：每个细胞的分解过程相互独立，总操作次数等于各细胞分解次数之和。对于单个活性值 \(x\)，每次选择一个质因数 \(p\)，将其替换为 \(p\) 个活性值为 \(x/p\) 的细胞。将 \(x\) 完全分解为 \(m=\Omega(x)\) 个质因数后，总操作次数等于按分解顺序的前缀积之和：\(g(x)=1+p_1+p_1p_2+\cdots+p_1p_2\cdots p_{m-1}\)。
-
算法选择：
- 质因数分解（试除法）：将每个 \(A_i\) 分解为不同质因数的集合
- 贪心排序：通过相邻交换论证可证，前缀积之和在质因数按从小到大排列时取最小值，按从大到小排列时取最大值
- 前缀积累加：用变量 \(cnt\) 维护当前前缀积，依次累加得到该细胞的最小/最大操作次数
-
关键步骤：
- 读取输入：\(N\) 和数组 \(A_{1..N}\)
- 质因数分解：对每个 \(A_i\) 用试除法求出所有不同质因数 \(p[1..cur]\)（如 \(12=2^2\times 3\) 记录 \(\{2,3\}\)）
- 计算最小值：从小到大遍历质因数，对每个质因数 \(p\) 不断除尽 \(num\)，每次执行
ans_min += cnt; cnt *= p; - 计算最大值：从大到小遍历质因数，执行同样的累乘逻辑
- 输出结果：
ans_min和ans_max
-
时间/空间复杂度：
- 时间复杂度：\(O(N\sqrt{\max A_i})\)，对每个数进行试除法分解（若预处理质数表可优化至 \(O(N\log A_i)\)）
- 空间复杂度：\(O(\log A_i)\)，存储单个数的质因数数组
-
贪心排序的核心思想：
- 展开式观察：设 \(x\) 的质因数（计重数）分解序列为 \(p_1,p_2,\dots,p_m\)，则总操作次数为 \(\sum_{i=0}^{m-1}\prod_{j=1}^{i}p_j\)（定义空积为 \(1\)）
- 相邻交换：若某处 \(p_i > p_{i+1}\)，交换二者后，后续所有项的乘积都会变小（因为小质数被更多项乘到），从而总和减小
- 最优策略：最小值对应从小到大排列，最大值对应从大到小排列
- 适用于涉及分解顺序优化的数论贪心问题
【算法标签】
约数
【代码详解】
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 200005;
int n, a[N];
int p[N], cur, ans_min, ans_max; // p: 存储质因数, cur: 质因数个数// 获取x的所有质因数
void fun(int x) {int cnt = 0;cur = 0; // 重置质因数计数器for (int i = 2; i * i <= x; i++) { // 只检查到√xif (x % i == 0) { // 找到质因数ip[++cur] = i; // 存储质因数while (x % i == 0) { // 除尽这个质因数x /= i;}}}if (x > 1) // 如果x还有剩余，那么x本身是质数p[++cur] = x;
}signed main() {cin >> n;for (int i = 1; i <= n; i++)cin >> a[i]; // 读取n个整数for (int i = 1; i <= n; i++) { // 对每个数字a[i]处理int num = a[i];fun(num); // 获取num的所有质因数// 计算最小值int cnt = 1;num = a[i];// 从小到大处理质因数while (num > 1) {for (int i = 1; i <= cur; i++) { // 从最小的质因数开始while (num % p[i] == 0) { // 当前质因数可整除num /= p[i];ans_min += cnt; // 累加当前乘积cnt *= p[i]; // 更新乘积}}}// 计算最大值cnt = 1;num = a[i];// 从大到小处理质因数while (num > 1) {for (int i = cur; i >= 1; i--) { // 从最大的质因数开始while (num % p[i] == 0) { // 当前质因数可整除num /= p[i];ans_max += cnt; // 累加当前乘积cnt *= p[i]; // 更新乘积}}}}cout << ans_min << " " << ans_max << endl;return 0;
}
【运行结果】
3
2 3 4
5 5