会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
这个问题可以转化为：将给定的正整数 T 分解为若干个大于等于 2 的整数 K_1, K_2, …, K_m，使得 ∏ K_i = T，求 ∑ K_i 的最小值。初始 X = 1，每次操作选择一个 K ≥ 2 并支付 K，相当于将 X 乘上 K。总成本即所有 K 的和，目标乘积为 T。
可以证明，当 T > 1 时，最优的分解方式是将其完全分解为质因数，最小总成本恰好等于 T 的所有质因数之和（包含重复）。原因如下：若分解中出现了合数 c=a×b（a,b≥2），将其替换为 a 和 b 后，成本变化为 a+b，而根据 (a−1)(b−1)≥1 可得 a+b≤a×b=c，且等号仅在 a=b=2 时成立。因此不断将合数拆分为更小的因数，成本不会增加，最终会得到全部由质数组成的分解，此时总和最小。对于 T=1，无需任何操作，成本为 0。
