4005. 使数组中所有元素相等的最小操作数 III 🔒
难度困难
题目描述
给定一个整数数组 nums。
在一次操作中，你可以选择任意元素 nums[i]，并执行以下操作之一：
- 乘法：将
nums[i]乘以一个整数k，其中k >= 2。 - 除法：将
nums[i]除以一个整数k，其中2 <= k < nums[i]，并且要求nums[i]可以被k整除。
返回使 nums 中所有元素 相等 所需的 最少操作次数。
示例 1：
输入： nums = [6,12,8]
输出： 3
解释：
我们可以执行以下操作，使所有数字变为 6：
- 将
nums[1] = 12除以 2，得到 6。 - 将
nums[2] = 8除以 4，得到 2。 - 将
nums[2] = 2乘以 3，得到 6。
示例 2：
输入： nums = [5,15,20]
输出： 2
解释：
我们可以执行以下操作，使所有数字变为 5：
- 将
nums[1] = 15除以 3，得到 5。 - 将
nums[2] = 20除以 4，得到 5。
示例 3：
输入： nums = [7,7,7]
输出： 0
解释：
所有元素已经相等，因此不需要任何操作。
约束条件：
1 <= nums.length <= 1051 <= nums[i] <= 109
解法
方法一
思考
\(n\) 达 \(10^5\)、元素达 \(10^9\)，不能对每一对元素模拟乘除，也不能把所有可达整数当作相等目标逐一验证。
一次乘法或一次整除就可以把一个数跳到它的任意倍数或真因数，因而会合到同一目标的代价由公因数以及各自还需补上或剥去的因子决定，而不是中间整数的个数。
为此应先按因数分解压缩每个数，再在规模远小于 \(10^9\) 的候选目标上累计最少操作。
1 | |
1 | |
1 | |
1 | |