2025-08-13：使数组包含目标值倍数的最少增量。用go语言，给出两个整数数组 nums 和 target。每一步可以把 nums 中的任意一个元素加 1。问至少需要多少次这样的加法操作，才能使得对 target 中的每一个值 t，最终的 nums 中都有至少一个数能够被 t 整除（即是 t 的倍数）。

1 <= nums.length <= 5 * 10000。

1 <= target.length <= 4。

target.length <= nums.length。

1 <= nums[i], target[i] <= 10000。

输入：nums = [8,4], target = [10,5]。

输出：2。

解释：

满足题目条件的最少操作次数是 2 。

将 8 增加到 10 ，需要 2 次操作，10 是目标值 5 和 10 的倍数。

题目来自力扣3444。

步骤描述

1. 预处理所有子集的最小公倍数（LCM）

• 使用掩码表示 target 数组的子集（长度为 m，掩码范围 0 到 (1<<m)-1）。
• 初始化 lcms[0] = 1（空集的 LCM 为 1）。
• 遍历每个 target 元素 t（索引 i）：
  • 对于每个已处理的掩码 mask，计算新掩码 mask | (1<<i) 的 LCM = lcm(t, lcms[mask])。
• 计算 lcm(a, b) 时，先求最大公约数（GCD），再用公式 a * b / GCD(a, b)（实际代码中为避免溢出，调整为 a / GCD(a, b) * b）。
• 时间复杂度：O(2^m * m)，由于 m <= 4，最多 16 个子集，常数时间。

2. 确定最大 LCM 阈值

• 计算 maxLcm = max(max(nums) * m, max(target))。
• 理由：任何元素最多增加 m 次（最坏情况），且目标值最大为 max(target)，超过此阈值的 LCM 无法通过增量达到，故后续可忽略。

3. 收集候选索引

• 初始化候选索引集合 candidateIndices（空集合）。
• 遍历每个非空子集掩码（从 1 到 (1<<m)-1）：
  • 若当前子集的 LCM > maxLcm，跳过。
  • 否则，维护一个大小为 m 的最大堆（堆顶为最大增量）：
    • 遍历 nums 中每个元素 x：
      • 计算增量：(lcm - x % lcm) % lcm（若 x 已是 lcm 的倍数，增量为 0）。
      • 若堆未满，将 (增量, 索引) 加入堆；否则，若当前增量小于堆顶增量，替换堆顶。
  • 遍历结束后，将堆中所有索引加入 candidateIndices（自动去重）。
• 时间复杂度：O(2^m * n)，其中 2^m 为子集数（最多 15），n 为 nums 长度。

4. 动态规划求解最小操作次数

• 状态定义：f[mask] 表示满足掩码 mask 对应的子集（mask 的二进制位表示 target 元素是否被满足）所需的最小操作次数。
• 初始化：
  • f[0] = 0（空集无需操作）。
  • 其他 f[mask] = 大数（如 math.MaxInt/2）。
• 状态转移：
  • 遍历每个候选索引 i（来自 candidateIndices）：
    • 从大到小遍历状态 j（从 (1<<m)-1 到 1）：
      • 枚举 j 的非空子集 sub（通过 sub = (sub-1) & j 迭代）：
        • 计算增量：(lcms[sub] - nums[i] % lcms[sub]) % lcms[sub]。
        • 更新：f[j] = min(f[j], f[j^sub] + 增量)。
• 目标：f[(1<<m)-1]（所有 target 元素均被满足）。
• 时间复杂度：O(|C| * 2^m * 2^m)，其中 |C| 为候选索引数（最多 64），2^m 为状态数（最多 16），子集枚举最多 2^m 次（常数）。

5. 返回结果

• 输出 f[(1<<m)-1] 作为最小操作次数。

复杂度分析

• 总时间复杂度：
  • 预处理 LCM：O(2^m * m) = O(16 * 4) = O(1)。
  • 收集候选索引：O(2^m * n) = O(15 * n) ≈ O(n)。
  • 动态规划：O(|C| * 2^{2m}) = O(64 * 256) = O(1)。
  • 整体：O(n)（线性）。
• 总额外空间复杂度：
  • LCM 数组：O(2^m) = O(16)。
  • 候选索引集合：O(2^m * m) = O(64)。
  • 堆：O(m) = O(4)。
  • 动态规划数组：O(2^m) = O(16)。
  • 整体：O(1)（常数空间，不依赖输入规模）。

示例说明

• 输入：nums = [8, 4], target = [10, 5]。
• 处理：
  1. 子集 LCM：{}:1, {10}:10, {5}:5, {10,5}:10。
  2. maxLcm = max(8*2, 10) = 16（全部保留）。
  3. 候选索引：
     • LCM=10：堆中索引 0（增量 2）、1（增量 6）。
     • LCM=5：堆中索引 0（增量 2）、1（增量 1）→ 加入索引 0,1。
  4. 动态规划：
     • 初始 f[00]=0, 其他无穷大。
     • 索引 0（元素 8）：
       • j=11：子集 11 → f[11]=min(∞, f[00]+2)=2。
       • j=10：子集 10 → f[10]=min(∞, f[00]+2)=2。
       • j=01：子集 01 → f[01]=min(∞, f[00]+2)=2。
     • 索引 1（元素 4）：
       • j=11：子集 11 → f[11]=min(2, f[00]+6)=2（不变）。
       • j=10：子集 10 → f[10]=min(2, f[00]+1)=1。
       • j=01：子集 01 → f[01]=min(2, f[00]+6)=2（不变）。
     • 最终 f[11]=2。
• 输出：2。

Go完整代码如下：

package main

import (
	"container/heap"
	"fmt"
	"math"
	"slices"
)

func minimumIncrements(nums []int, target []int) int {
	m := len(target)
	lcms := make([]int, 1<<m)
	lcms[0] = 1
	for i, t := range target {
		bit := 1 << i
		for mask, l := range lcms[:bit] {
			lcms[bit|mask] = lcm(t, l)
		}
	}

	maxLcm := max(slices.Max(nums)*m, slices.Max(target))
	candidateIndices := map[int]struct{}{}
	for _, l := range lcms[1:] {
		if l > maxLcm {
			continue
		}
		h := hp{}
		for i, x := range nums {
			p := pair{(l - x%l) % l, i}
			if len(h) < m {
				heap.Push(&h, p)
			} else {
				h.update(p)
			}
		}
		for _, p := range h {
			candidateIndices[p.i] = struct{}{}
		}
	}

	f := make([]int, 1<<m)
	for j := 1; j < 1<<m; j++ {
		f[j] = math.MaxInt / 2
	}
	for i := range candidateIndices {
		x := nums[i]
		for j := 1<<m - 1; j > 0; j-- {
			for sub := j; sub > 0; sub = (sub - 1) & j {
				l := lcms[sub]
				f[j] = min(f[j], f[j^sub]+(l-x%l)%l)
			}
		}
	}
	return f[1<<m-1]
}

func gcd(a, b int) int {
	for a != 0 {
		a, b = b%a, a
	}
	return b
}
func lcm(a, b int) int { return a / gcd(a, b) * b }

type pair struct{ op, i int }
type hp []pair

func (h hp) Len() int           { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].op > h[j].op }
func (h hp) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any)        { *h = append(*h, v.(pair)) }
func (hp) Pop() (_ any)         { return }
func (h *hp) update(p pair) {
	if p.op < (*h)[0].op {
		(*h)[0] = p
		heap.Fix(h, 0)
	}
}

func main() {
	nums := []int{8, 4}
	target := []int{10, 5}
	result := minimumIncrements(nums, target)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

import heapq
import math
from math import gcd
from typing import List

def lcm(a: int, b: int) -> int:
    return a * b // gcd(a, b)

def minimum_increments(nums: List[int], target: List[int]) -> int:
    m = len(target)
    n = len(nums)
    total_mask = 1 << m
    
    # 计算所有子集的最小公倍数
    lcms = [1] * total_mask
    for i in range(m):
        bit = 1 << i
        for mask in range(bit):
            new_mask = mask | bit
            lcms[new_mask] = lcm(lcms[mask], target[i])
    
    # 计算最大LCM用于过滤
    max_lcm_val = max(max(nums) * m, max(target))
    
    # 收集候选索引
    candidate_set = set()
    for mask in range(1, total_mask):
        l_val = lcms[mask]
        if l_val > max_lcm_val:
            continue
        
        heap = []
        for idx, x in enumerate(nums):
            cost = (l_val - x % l_val) % l_val
            if len(heap) < m:
                heapq.heappush(heap, (-cost, idx))
            else:
                if cost < -heap[0][0]:
                    heapq.heapreplace(heap, (-cost, idx))
        
        for neg_cost, idx in heap:
            candidate_set.add(idx)
    
    # 动态规划
    f = [10**18] * total_mask
    f[0] = 0
    
    for idx in candidate_set:
        x = nums[idx]
        # 倒序遍历所有状态
        for j in range(total_mask - 1, 0, -1):
            # 枚举所有非空子集
            sub = j
            while sub > 0:
                l_val = lcms[sub]
                cost = (l_val - x % l_val) % l_val
                prev_state = j ^ sub
                if f[prev_state] + cost < f[j]:
                    f[j] = f[prev_state] + cost
                sub = (sub - 1) & j
    
    return f[total_mask - 1]

# 测试用例
if __name__ == "__main__":
    nums = [8, 4]
    target = [10, 5]
    print(minimum_increments(nums, target))  # 输出: 3