题解 | #1=N#

问题分析

本问题的核心是将一个正整数 分解为若干个整数 的乘积（即 ），使得这些因数的总和 最小。

讨论： 我们需要权衡“一次性增加大的 ”还是“多次增加小的 ”。例如达到 ：

• 方案 A：一次性选择 ，成本为 6。
• 方案 B：先选 ，再选 ，成本为 。 显而易见，分解能够降低总成本。

算法策略：质因数分解 (Prime Factorization)

1. 数学原理

为了最小化成本，我们需要研究什么情况下将一个合数 分解为 会使成本降低。 设 ，其中 。 我们比较分解前后的成本：

• 不分解的总成本：
• 分解后的总成本：

考察差值：。

• 当 时，，即 。此时分解与不分解成本一致（均为 4）。
• 当 且其中一个大于 2 时，，即 。此时分解后的成本一定更小。

结论： 由于任何合数（除了 4 以外）分解为两个因子的和都小于其本身，而 4 分解为 成本不变，因此将 彻底分解为质因数序列，其质量因数的总和即为最小成本。

2. 算法

本题采用贪心策略 (Greedy Strategy) 结合 数论基础。在每一步操作中，我们都尽可能地将当前的因子拆解为更小的因子，直到无法再拆解（即变为质数）为止。

复杂度分析

时间复杂度

采用基础的质因数分解算法：

• 逻辑： 遍历从 2 到 的所有整数。如果当前数 能整除 ，则循环除去 。
• 复杂度： 。

空间复杂度

• 复杂度： 。
• 分析： 只需要常数级别的变量来存储当前的 值和累加的成本（Cost），无需额外的存储结构。

代码实现

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    int cost = 0;
    if (n == 1) {
        cout << 0 << endl;
        return 0;
    }

    for (int i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            n /= i;
            cost += i;
        }
    }
    if (n > 1) {
        cost += n;
    }
    cout << cost << endl;
}