2025-08-13：使数组包含目标值倍数的最少增量。用go语言，给出两个整数数组 nums 和 target。每一步可以把 n

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}
            iflen(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           { returnlen(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)
}

# -*-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
            iflen(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