2026-08-22：可整除替换后的数组最小元素和。用go语言，给定一个整数数组。你可以反复执行这种操作：任意选出两个位置，如果其中一个位置上的数能被另一个位置上的数整除，就把那个“倍数”位置的数改成

2026-08-22可整除替换后的数组最小元素和。用go语言给定一个整数数组。你可以反复执行这种操作任意选出两个位置如果其中一个位置上的数能被另一个位置上的数整除就把那个“倍数”位置的数改成“除数”位置的数。每次替换后被改动的数只会变小或保持不变。请问经过任意多次这样的操作整个数组所有数的总和最小可以变成多少1 nums.length 100000。1 nums[i] 100000。输入 nums [3,6,2]。输出 7。解释选择 a 1、b 2此时 nums[a] 6nums[b] 2。由于 6 % 2 0将 nums[1] 替换为 nums[2]。数组变为 [3, 2, 2]。之后无法再通过操作减少元素和。因此最终元素和为 3 2 2 7。题目来自力扣3927。分步骤详解第一步预处理所有数的因子表代码中定义了一个全局的二维切片divisors大小为 100001因为题目限制 nums[i] ≤ 100000。在init函数中枚举外层循环 i 从 1 到 100000内层循环 j 从 i 开始每次增加 i直到超过 100000对于每个 j把 i 追加到divisors[j]中表示 i 是 j 的一个因子例如当 i1会把 1 加到所有 1~100000 的因子列表里当 i2会把 2 加到 2,4,6,8,… 的因子列表里结果divisors[x]里存放的是 x 的所有正因子并且是按从小到大顺序存放的因为外层 i 从小到大。第二步统计数组元素出现次数使用一个字典cntmap[int]int来统计每个数字在数组中出现的次数。这样做的目的相同的数字操作结果一样无需重复计算可以节省时间。第三步遍历每个不同的数字找到它能变成的最小可行值对于cnt中的每个键x及其出现次数c我们想要把当前所有值为 x 的元素替换成某个更小的数并且这个数必须是数组中存在的因为要作为“除数”。因为因子列表是按从小到大的顺序我们直接遍历divisors[x]检查该因子是否在cnt中存在即数组里有这个数。一旦找到第一个存在的因子d就可以将所有这 c 个 x 都替换成 d因为 d ≤ x且这是能取得的最小可行替换值因子从小到大。累加ans d * c然后立即跳出循环因为只需最小的那个因子即可。关键点如果一个数 x 最小的因子 1 在数组中存在那么它可以直接变成 1这是最优的。如果 x 本身就在数组中即因子 x 存在其实它在遍历因子时最早遇到的是 1如果1存在否则可能遇到更小的因子但最差就是因子 x 本身此时替换成自己不变。第四步返回最小总和累加完所有不同数字对应的最小可能值乘以其出现次数就得到了整个数组的最小总和。示例运行过程nums[3,6,2]统计cnt {3:1, 6:1, 2:1}处理 x3因子列表1,3检查1是否在cnt → 不存在检查3是否在cnt → 存在所以变成3ans 3处理 x6因子列表1,2,3,6检查1 → 不存在检查2 → 存在变成2ans 2处理 x2因子列表1,2检查1 → 不存在检查2 → 存在变成2ans 2最终 ans 322 7时间复杂度分析预处理因子表双层循环外层 100000 次内层总迭代次数约为n * (1/1 1/2 ... 1/n)≈ n log n。这里 n100000所以大约 100000 * log(100000) ≈ 1.2e6 次操作非常快。统计次数O(N)N 是数组长度最多 100000。每个不同数字查找最小因子最坏情况每个数要遍历它的所有因子。所有不同数字的总因子数量就是所有出现过的数字的因子个数总和。在最坏情况下数组包含 1~100000 的所有数因子总数同样约为 N log N。且每个因子检查只是 map 查找 O(1)。总时间复杂度预处理 O(M log M) 主逻辑 O(M log M)M100000即O(M log M)其中 M 是数值上限100000与数组长度 N 和数值范围有关。额外空间复杂度分析divisors二维切片存储所有数的所有因子总数量约为 M log M ≈ 1.2e6 个整数占用空间 O(M log M)。cntmap最多存放不同数字个数 ≤ min(N, M)空间 O(min(N, M))。总体额外空间O(M log M)因为预处理表是主要占用。最终答案总结算法通过预处理因子表并利用出现次数字典对每个不同的数找到数组中出现的最小因子来进行替换保证总和最小。时间复杂度O(M log M)M100000近乎常数规模额外空间复杂度O(M log M)Go完整代码如下packagemainimport(fmt)constmx100_001vardivisors[mx][]intfuncinit(){fori:1;imx;i{forj:i;jmx;ji{// 枚举 i 的倍数 jdivisors[j]append(divisors[j],i)// i 是 j 的因子}}}funcminArraySum(nums[]int)(ansint64){cnt:map[int]int{}for_,x:rangenums{cnt[x]}forx,c:rangecnt{// 遍历 cnt 而不是 nums这样重复元素只会计算一次for_,d:rangedivisors[x]{// 从小到大枚举 x 的因子 difcnt[d]0{ansint64(d)*int64(c)// 把 x 变成 d 是最优的break}}}return}funcmain(){nums:[]int{3,6,2}result:minArraySum(nums)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-fromcollectionsimportCounter MX100_001divisors[[]for_inrange(MX)]# 预处理因子divisors[j] 保存 j 的所有因子且按从小到大排列foriinrange(1,MX):forjinrange(i,MX,i):divisors[j].append(i)defmin_array_sum(nums):cntCounter(nums)ans0forx,cincnt.items():fordindivisors[x]:# 从小到大枚举 x 的因子ifcnt[d]0:ansd*c# 把 x 变成 dbreakreturnansdefmain():nums[3,6,2]resultmin_array_sum(nums)print(result)if__name____main__:main()C完整代码如下#includeiostream#includevector#includeunordered_mapusingnamespacestd;constintMX100001;vectorvectorintdivisors(MX);voidinit_divisors(){for(inti1;iMX;i){for(intji;jMX;ji){// 枚举 i 的倍数 jdivisors[j].push_back(i);// i 是 j 的因子}}}longlongminArraySum(constvectorintnums){unordered_mapint,intcnt;for(intx:nums){cnt[x];}longlongans0;for(constauto[x,c]:cnt){for(intd:divisors[x]){// 从小到大枚举 x 的因子autoitcnt.find(d);if(it!cnt.end()it-second0){ans1LL*d*c;// 把 x 变成 dbreak;}}}returnans;}intmain(){init_divisors();vectorintnums{3,6,2};longlongresultminArraySum(nums);coutresultendl;return0;}