核心思路:将 N 分解为质因数的乘积,最小成本就是所有质因数(包括重复的)之和。
原因:当 a, b>=2 时,a+b<=a*b 恒成立,因此分解为(最小)质因数的成本最低。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
scanner.close();
System.out.println(minCost(N));
}
private static int minCost(int n) {
if (n == 1) return 0;
int cost = 0;
// 分解质因数
for (int i = 2; i * i <= n; i++) {
// 计算质因数i的指数
while (n % i == 0) {
cost += i; // 累加质因数作为成本
n /= i;
}
}
// 如果剩余的n是一个质数
if (n > 1) {
cost += n;
}
return cost;
}
}

京公网安备 11010502036488号