题解 | #最小乘积代价和#

题目链接

题目描述

给定一个正整数 $N$ ，初始值为 $N$ 。你可以进行若干次操作：选择一个整数 $K \ge 2$ ，支付 $K$ 的代价，将当前值变为其与 $K$ 的商。要求每次操作的 $K$ 都必须是当前值的因子。请计算将 $N$ 恰好变为 $1$ 所需要支付的最小总代价。

解题思路

本题的本质是一个最优化问题，我们可以将其转化为一个经典的数论问题。

问题转化：假设我们进行了一系列操作，选择的除数依次为 $K_1, K_2, \dots, K_m$ 。那么操作过程可以表示为：

$N \xrightarrow{/K_1} N/K_1 \xrightarrow{/K_2} N/(K_1 \cdot K_2) \dots \xrightarrow{/K_m} N/(K_1 \cdot K_2 \cdot \dots \cdot K_m) = 1$

这说明 $N = K_1 \cdot K_2 \cdot \dots \cdot K_m$ 。我们的目标是最小化总代价，即最小化 $\sum_{i=1}^{m} K_i$ 。

因此，问题等价于：将数 $N$ 分解为若干个大于等于2的整数的乘积，并求这些整数的最小和。
核心洞察：考虑任意一个合数因子 $C$ 。假设 $C = A \cdot B$ ，其中 $A, B \ge 2$ 。在我们的因子和中，我们可以用 $A+B$ 来替换 $C$ 。由于 $A, B \ge 2$ ，我们可以推断 $A+B \le A \cdot B$ （仅当 $A=B=2$ 时取等号，其他情况均有 $A+B < A \cdot B$ ）。这意味着，将任何合数因子进一步分解为其因子，总能使因子之和变得更小或保持不变。
最优策略：为了使因子之和最小，我们必须将 $N$ 分解到不能再分解为止，也就是将 $N$ 完全分解为其质因数。最小的总代价就是 $N$ 所有质因数的总和。
算法实现：
- 我们使用试除法来找出 $N$ 的所有质因数。
- 从 $i=2$ 开始循环，直到 $i \cdot i \le N$ 。
- 对于每个 $i$ ，用一个内部 while 循环来判断 $N$ 是否能被 $i$ 整除。只要能整除，就将 $i$ 加入总代价中，并更新 $N$ 为 $N/i$ 。
- 外层循环结束后，如果 $N$ 仍然大于 $1$ ，说明剩下的这个 $N$ 本身也是一个质因数，需要将其加入总代价。

代码

c++
java
python

#include <iostream>
#include <cmath>

using namespace std;

int main() {
    long long n;
    cin >> n;
    
    long long total_cost = 0;
    for (long long i = 2; i * i <= n; ++i) {
        while (n % i == 0) {
            total_cost += i;
            n /= i;
        }
    }
    
    if (n > 1) {
        total_cost += n;
    }
    
    cout << total_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 total_cost = 0;
        for (long i = 2; i * i <= n; ++i) {
            while (n % i == 0) {
                total_cost += i;
                n /= i;
            }
        }
        
        if (n > 1) {
            total_cost += n;
        }
        
        System.out.println(total_cost);
    }
}

import math

n = int(input())

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

if temp_n > 1:
    total_cost += temp_n

print(total_cost)

算法及复杂度

算法：数论、质因数分解
时间复杂度：算法的核心是试除法，循环最多执行到 $\sqrt{N}$ 次。因此，时间复杂度为 $\mathcal{O}(\sqrt{N})$ 。
空间复杂度：算法仅使用了少数变量来存储中间结果，因此空间复杂度为 $\mathcal{O}(1)$ 。