题目链接

HIGH6 最小乘积代价和

题目描述

给定一个正整数 N，你可以进行如下操作：

  • 选择 N 的一个大于 1 的约数 K。
  • 支付 K 的代价。
  • 将 N 更新为 N / K。

重复此操作，直到 N 变为 1。请计算将 N 变为 1 所需要的最小总代价。

解题思路

这是一个可以用动态规划解决，但最终可以简化为贪心策略的优化问题。

1. 动态规划思路

我们可以定义 dp[i] 为将数字 i 变为 1 所需的最小代价。我们的目标是求 dp[N]。 根据题意，状态转移方程为： dp[i] = min(K + dp[i / K))，其中 K 是 i 的所有大于 1 的约数。 基本情况是 dp[1] = 0。

让我们尝试计算几个值：

  • dp[1] = 0
  • dp[2] = 2 + dp[1] = 2
  • dp[3] = 3 + dp[1] = 3
  • dp[4] = min(2 + dp[2], 4 + dp[1]) = min(2 + 2, 4 + 0) = 4
  • dp[6] = min(2 + dp[3], 3 + dp[2], 6 + dp[1]) = min(2 + 3, 3 + 2, 6) = 5

2. 贪心优化

在 DP 的计算中，我们发现一个规律。考虑选择一个合数约数 K，其中 K = a * b (a, b > 1)。

  • 选择 K 的代价是 K + dp[N / K] = a * b + dp[N / (a * b)]。
  • 如果我们不选择 K，而是分两步，先选择 a 再选择 b，代价会是多少？
    • a + dp[N / a] = a + (b + dp[(N/a) / b]) = a + b + dp[N / (a * b)]。

比较这两种策略的代价：

  • a * b + dp[N / (a * b)] vs a + b + dp[N / (a * b)]
  • 因为 a, b > 1，我们总是有 a * b >= a + b （仅在 a=b=2 时取等）。
  • 这意味着，选择一个合数约数 K 的代价，总是大于或等于先选择 K 的一个质因子 p，然后再处理剩下部分的代价。
  • 因此，我们的最优策略永远是只选择质因子进行操作。

3. 最终算法

问题被简化为：将 N 分解为其所有质因子的乘积 N = p1 * p2 * ... * pk，其最小代价就是这些质因子的总和 p1 + p2 + ... + pk。 这和我们之前做过的“分解质因数”问题非常相似，我们只需将分解出的所有质因子累加起来即可。

算法流程：

  • 输入 N（注意使用 long long）。
  • 初始化总代价 cost = 0。
  • 使用试除法，从 i = 2 循环到 sqrt(N)。
  • 对于每个 i，循环判断 N 是否能被 i 整除，如果可以，就将 i 加入 cost，并更新 N。
  • 循环结束后，如果 N > 1，说明剩下的 N 是一个大质数，也将其加入 cost。
  • 输出 cost。

代码

#include <iostream>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long n;
    cin >> n;

    long long cost = 0;
    for (long long i = 2; i * i <= n; ++i) {
        while (n % i == 0) {
            cost += i;
            n /= i;
        }
    }

    if (n > 1) {
        cost += n;
    }

    cout << cost << endl;

    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 cost = 0;
        for (long i = 2; i * i <= n; i++) {
            while (n % i == 0) {
                cost += i;
                n /= i;
            }
        }

        if (n > 1) {
            cost += n;
        }

        System.out.println(cost);
    }
}

n = int(input())

cost = 0
i = 2
while i * i <= n:
    while n % i == 0:
        cost += i
        n //= i
    i += 1

if n > 1:
    cost += n

print(cost)

算法及复杂度

  • 算法：动态规划、贪心、质因数分解
  • 时间复杂度：，主要开销来自于试除法分解质因数。
  • 空间复杂度：，我们只需要常数级别的额外空间。