题目链接

1=N

题目描述

给定一个正整数 。你可以对一个整数执行以下操作（不限次数）：选择一个大于等于 2 的整数 ，支付 的成本，然后将当前的数变为原来的 。请问，将 变为 1 所需的最小总成本是多少？

解题思路

本题要求将数字 通过一系列除法操作变为 1，并最小化操作成本之和。每次操作选择一个除数 ，成本就是 。

假设我们选择了一系列的除数 ，使得 最终变为 1。这意味着 。我们的目标是最小化总成本 。

问题就转化为了：将 分解为若干个大于等于 2 的整数的乘积，如何使得这些整数的和最小？

我们可以得出一个重要的结论：要使和最小，分解出来的所有因子都必须是质数。

我们可以用反证法来思考：假设在最优分解中，存在一个合数因子 （其中 ）。我们可以将这个因子 替换为它的两个更小的因子 和 。

  • 替换前，乘积中包含 ，和中包含 。
  • 替换后，乘积中包含 和 ，和中包含 和 。 由于 （即 ），我们总有 。等号仅在 时成立。这意味着用 替换 会使总和不变或变得更小。因此，将任何合数因子继续分解为其质因子的乘积，总能得到一个不劣（甚至更优）的结果。

所以，最优解一定是将 分解为其所有质因子的乘积。最小成本就是 的所有质因子之和（包括重复的质因子）。

例如，对于 ：

  • 质因数分解为 。
  • 最小成本为 。

因此，算法就是对 进行质因数分解，并累加所有质因子。我们可以使用试除法来高效地完成这个任务。

代码

#include <iostream>

using namespace std;

int main() {
    long long n;
    cin >> n;
    long long sum = 0;

    // 试除法分解质因数
    for (long long i = 2; i * i <= n; ++i) {
        while (n % i == 0) {
            sum += i;
            n /= i;
        }
    }
    // 如果 n 最后还剩下大于 1 的数，那么它一定是一个质数
    if (n > 1) {
        sum += n;
    }

    cout << sum << "\n";
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long sum = 0;

        // 试除法分解质因数
        for (long i = 2; i * i <= n; ++i) {
            while (n % i == 0) {
                sum += i;
                n /= i;
            }
        }
        // 如果 n 最后还剩下大于 1 的数，那么它一定是一个质数
        if (n > 1) {
            sum += n;
        }

        System.out.println(sum);
    }
}

n = int(input())
total_cost = 0

# 试除法分解质因数
i = 2
while i * i <= n:
    while n % i == 0:
        total_cost += i
        n //= i
    i += 1

# 如果最后 n 还大于 1，说明剩下的 n 也是一个质因数
if n > 1:
    total_cost += n

print(total_cost)

算法及复杂度

  • 算法：试除法（质因数分解）
  • 时间复杂度：，其中 是输入的整数。循环最多执行到 。
  • 空间复杂度：，只需要常数个变量来存储中间结果。