2026-10-09可整除游戏。用go语言有一个长度为 n 的整数数组 nums。Alice 和 Bob 要进行一轮比较。Alice 先选一个大于 1 的整数 k再选数组里的一个连续区间用左右端点 l 和 r 表示其中 0 l r n。两人的初始得分都为 0。接下来只处理这个区间内的每个元素如果某个元素能被 k 整除就把它的值加到 Alice 的得分上如果不能被 k 整除就把它的值加到 Bob 的得分上。把 Alice 的总得分减去 Bob 的总得分得到两人的差距。Alice 想让这个差距尽量大如果有多个 k 都能达到同样的最大差距她会选其中最小的那个 k。最后把这个最大差距与 Alice 选中的 k 相乘并对 1000000007 取余返回得到的余数。1 nums.length 1000。1 nums[i] 1000000。输入 nums [1,4,6,8]。输出 36。解释Alice 可以选择 k 2、l 1 和 r 3。nums[1…3] 中的所有值都能被 2 整除因此 Alice 的分数为 4 6 8 18Bob 的分数为 0。分数差为 18这是可能达到的最大值。在所有能达到该分数差的 k 中最小的是 2。因此答案为 18 * 2 36。题目来自力扣3984。大体步骤如下第一步预处理每个数的质因子代码一开始定义了一个最大值mx 1_000_001因为题目中nums[i] 1_000_000。然后建立一个全局的二维列表primeDivisors用来保存每个整数有哪些不同的质因子。预处理方式类似埃氏筛从 2 开始遍历到mx - 1。如果当前数字i还没有被记录过任何质因子就说明i是质数。对于这个质数i枚举它在mx范围内的所有倍数j即j i, 2i, 3i, ...。把质数i加入到primeDivisors[j]中表示i是j的一个质因子。由于外层只对质数执行加入操作所以每个数最终得到的都是它所有不同的质因子不会有重复。这样做的好处是后面需要知道某个nums[i]能被哪些质数整除时可以直接查表不需要临时分解质因数。第二步计算前缀和对于数组nums代码建立一个长度为n 1的前缀和数组sum。sum[0] 0sum[i 1] sum[i] nums[i]这样任意区间[l, r]内所有元素的总和就可以用sum[r 1] - sum[l]快速得到。后面在计算某些元素对分数差的负贡献时会用到这个前缀和。第三步处理特殊情况——所有元素都是 1如果sum[n] n因为题目保证nums[i] 1所以这意味着数组里的每一个元素都等于 1。此时无论 Alice 选择什么k 11 都不可能被k整除。因此区间内所有元素都会加到 Bob 的分数上Alice 的分数始终为 0。为了让分数差最大Alice 只能选择一个只包含一个元素的区间。这样Alice 得分 0Bob 得分 1分数差 0 - 1 -1所有k都能达到这个最大分数差 -1所以 Alice 会选择最小的k 2。乘积为-1 * 2 -2。对1_000_000_007取余相当于返回1_000_000_007 - 2 1_000_000_005。代码中直接返回mod - 2就是处理这个特殊情况。第四步初始化动态维护的状态如果数组不是全 1代码进入主要逻辑。定义两个映射f[p]对于候选质数p记录当前以最近一次能被p整除的元素结尾时能够得到的最大分数差。last[p]记录上一次更新f[p]时对应的位置信息具体是那个元素下标加 1也就是前缀和中的下标。同时初始化全局变量maxDiff目前发现的最大分数差初始为极小值。bestK达到当前最大分数差的最小质数k初始为 0。这里只考虑质数作为候选k。原因是如果某个合数k能整除某些元素那么k的任意一个质因子也一定能整除这些元素。换成这个质因子作为k可被 Alice 拿走的元素集合只会变大或不变分数差不会变差。而且质因子更小若分数差相同Alice 会优先选更小的k。所以最优的k一定可以取某个质数代码只需枚举每个nums[i]的质因子。第五步遍历数组并更新状态代码从左到右遍历数组nums对于每个下标i和元素x如果x 2它没有质因子跳过。否则取出x的所有不同质因子p。对于每一个质因子p进行以下计算从上次更新f[p]的位置last[p]到当前位置i之间所有元素都不能被p整除。因为如果中间有元素能被p整除last[p]就会在那时被更新不会留到现在。因此这些中间元素如果放入区间对分数差的贡献都是负数即-nums[j]。这些中间元素的总和可以通过前缀和计算sum[i] - sum[last[p]]。如果延续之前的区间那么新的分数差会是f[p] - (sum[i] - sum[last[p]]) x也就是f[p] - sum[i] sum[last[p]] x。但是如果这个值在减去中间负贡献后变得小于 0那么不如放弃之前的区间直接从当前元素x重新开始。因此代码取max(f[p] - sum[i] sum[last[p]], 0) x作为新的diff。这个diff就是以质数p为k且区间右端点当前在i时能得到的最大分数差。把f[p]更新为这个diff。把last[p]更新为i 1表示下一次计算中间负贡献时从当前位置之后开始。更新全局最优如果当前diff大于maxDiff则更新maxDiff diff并令bestK p。如果当前diff等于maxDiff并且p比当前的bestK更小则更新bestK p。这样保证在最大分数差相同的情况下最终选到最小的质数k。遍历结束后maxDiff就是所有可能区间和所有可能质数k中能达到的最大分数差bestK就是达到该最大分数差的最小质数。第六步返回结果最后代码计算maxDiff * bestK % 1_000_000_007并返回这个余数。算法正确性简述枚举所有nums[i]的质因子等价于枚举了所有可能成为最优k的质数。对于每个质数p代码实际上是在用类似 Kadane 最大子段和的思想寻找以某个位置结尾、且只考虑p能否整除元素时的最大分数差。中间不能被p整除的元素贡献为负代码通过前缀和差值一次性扣除并用max(..., 0)实现“如果之前区间变成负贡献就重新开始”。全局比较所有质数的结果并记录最大差和最小k。时间复杂度预处理质因子最大值设为MX 1_000_001。外层枚举质数内层枚举质数的倍数。总操作次数约为MX * (1/2 1/3 1/5 ...)即O(MX log log MX)。由于MX是固定常数 1,000,001这部分可以看作预处理开销。游戏主循环遍历数组nums每个元素最多分解出约 7 个不同质因子因为1_000_000以内不同质因子个数最多为 7。所以主循环复杂度为O(n * ω(max(nums)))其中ω表示不同质因子个数最大不超过 7。因此总时间复杂度为O(MX log log MX n * ω(max(nums)))。在题目约束下n 1000所以主循环非常小预处理占主要部分。额外空间复杂度primeDivisors存储每个数的所有不同质因子。总存储量约为MX * 平均质因子个数量级为O(MX log log MX)。前缀和数组sum长度为n 1空间O(n)。两个映射f和last只存储实际出现过的质数最多不超过n * 7个键空间O(n * ω(max(nums)))也可简化为O(n)级别。所以总额外空间复杂度为O(MX log log MX n)。如果按最坏情况估计预处理数组占主导大约为O(MX log log MX)。Go完整代码如下packagemainimport(fmtmath)constmx1_000_001varprimeDivisors[mx][]int32// 预处理每个数的质因子funcinit(){fori:int32(2);imx;i{ifprimeDivisors[i]nil{// i 是质数forj:i;jmx;ji{// 枚举 i 的倍数 jprimeDivisors[j]append(primeDivisors[j],i)// i 是 j 的质因子}}}}funcdivisibleGame(nums[]int)(ansint){constmod1_000_000_007n:len(nums)sum:make([]int,n1)fori,x:rangenums{sum[i1]sum[i]x}ifsum[n]n{// 每个数都是 1// 最优是只选一个 1分数差为 -1最小 k 为 2returnmod-2}f:map[int32]int{}last:map[int32]int{}maxDiff,bestK:math.MinInt,int32(0)fori,x:rangenums{for_,p:rangeprimeDivisors[x]{diff:max(f[p]-sum[i]sum[last[p]],0)x f[p]diffifdiffmaxDiff||diffmaxDiffpbestK{maxDiff,bestKdiff,p}last[p]i1}}returnmaxDiff*int(bestK)%mod}funcmain(){nums:[]int{1,4,6,8}result:divisibleGame(nums)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-defdivisible_game(nums):MOD1_000_000_007nlen(nums)# 所有元素都是 1 的特殊情况ifsum(nums)n:returnMOD-2max_valmax(nums)ifnumselse1# 预处理最小质因子SPFspflist(range(max_val1))foriinrange(2,int(max_val**0.5)1):ifspf[i]i:forjinrange(i*i,max_val1,i):ifspf[j]j:spf[j]i# 前缀和prefix[0]*(n1)fori,xinenumerate(nums):prefix[i1]prefix[i]x f{}last{}max_diff-10**18best_k0fori,xinenumerate(nums):ifx1:continue# 分解出 x 的所有不同质因子tempx factors[]whiletemp1:pspf[temp]factors.append(p)whiletemp%p0:temp//pforpinfactors:prev_ff.get(p,0)prev_lastlast.get(p,0)diffmax(prev_f-prefix[i]prefix[prev_last],0)x f[p]diffifdiffmax_diffor(diffmax_diffandpbest_k):max_diffdiff best_kp last[p]i1returnmax_diff*best_k%MODif__name____main__:nums[1,4,6,8]print(divisible_game(nums))C完整代码如下#includeiostream#includevector#includealgorithm#includeclimitsusingnamespacestd;constintMX1000001;vectorvectorintprimeDivisors(MX);// 预处理每个数的质因子voidinit(){for(inti2;iMX;i){if(primeDivisors[i].empty()){// i 是质数for(intji;jMX;ji){primeDivisors[j].push_back(i);// i 是 j 的质因子}}}}intdivisibleGame(vectorintnums){constlonglongMOD1000000007LL;intnnums.size();vectorlonglongsum(n1,0);for(inti0;in;i){sum[i1]sum[i]nums[i];}if(sum[n]n){// 每个数都是 1// 最优是只选一个 1分数差为 -1最小 k 为 2return(MOD-2)%MOD;}vectorlonglongf(MX,0);vectorintlast(MX,0);longlongmaxDiffLLONG_MIN;intbestK0;for(inti0;in;i){intxnums[i];if(x2)continue;// 没有质因子for(intp:primeDivisors[x]){longlongdiffmax(f[p]-sum[i]sum[last[p]],0LL)x;f[p]diff;if(diffmaxDiff||(diffmaxDiffpbestK)){maxDiffdiff;bestKp;}last[p]i1;}}return(maxDiff%MOD)*(bestK%MOD)%MOD;}intmain(){init();vectorintnums{1,4,6,8};intresultdivisibleGame(nums);coutresultendl;return0;}