2026-10-09：可整除游戏。用go语言，有一个长度为 n 的整数数组 nums。Alice 和 Bob 要进行一轮比较。Alice 先选一个大于 1 的整数 k，再

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 = 18，Bob 的分数为 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] = 0

• •sum[i + 1] = sum[i] + nums[i]

这样，任意区间[l, r]内所有元素的总和就可以用sum[r + 1] - sum[l]快速得到。后面在计算某些元素对分数差的负贡献时，会用到这个前缀和。

第三步：处理特殊情况——所有元素都是 1

如果sum[n] == n，因为题目保证nums[i] >= 1，所以这意味着数组里的每一个元素都等于 1。

此时，无论 Alice 选择什么k > 1，1 都不可能被k整除。因此区间内所有元素都会加到 Bob 的分数上，Alice 的分数始终为 0。

为了让分数差最大，Alice 只能选择一个只包含一个元素的区间。这样：

• • Alice 得分 0

• • Bob 得分 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：

1. 1. 如果x < 2，它没有质因子，跳过。

2. 2. 否则，取出x的所有不同质因子p。

3. 3. 对于每一个质因子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，表示下一次计算中间负贡献时，从当前位置之后开始。

4. 更新全局最优：

• • 如果当前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完整代码如下：

package main

 import (
    "fmt"
    "math"
)

 const mx = 1_000_001

 var primeDivisors [mx][]int32

 // 预处理每个数的质因子
func init() {
    for i := int32(2); i < mx; i++ {
        if primeDivisors[i] == nil { // i 是质数
            for j := i; j < mx; j += i { // 枚举 i 的倍数 j
                primeDivisors[j] = append(primeDivisors[j], i) // i 是 j 的质因子
            }
        }
    }
}

 func divisibleGame(nums []int) (ans int) {
    const mod = 1_000_000_007

     n := len(nums)
    sum := make([]int, n+1)
    for i, x := range nums {
        sum[i+1] = sum[i] + x
    }

     if sum[n] == n {
        // 每个数都是 1
        // 最优是只选一个 1（分数差为 -1），最小 k 为 2
        return mod - 2
    }

     f := map[int32]int{}
    last := map[int32]int{}
    maxDiff, bestK := math.MinInt, int32(0)

     for i, x := range nums {
        for _, p := range primeDivisors[x] {
            diff := max(f[p]-sum[i]+sum[last[p]], 0) + x
            f[p] = diff
            if diff > maxDiff || diff == maxDiff && p < bestK {
                maxDiff, bestK = diff, p
            }
            last[p] = i + 1
        }
    }

     return maxDiff * int(bestK) % mod
}

 func main() {
    nums := []int{1, 4, 6, 8}
    result := divisibleGame(nums)
    fmt.Println(result)
}

Python完整代码如下：

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

 def divisible_game(nums):
    MOD = 1_000_000_007
    n = len(nums)

     # 所有元素都是 1 的特殊情况
    if sum(nums) == n:
        return MOD - 2

     max_val = max(nums) if nums else1

     # 预处理最小质因子（SPF）
    spf = list(range(max_val + 1))
    for i in range(2, int(max_val ** 0.5) + 1):
        if spf[i] == i:
            for j in range(i * i, max_val + 1, i):
                if spf[j] == j:
                    spf[j] = i

     # 前缀和
    prefix = [0] * (n + 1)
    for i, x in enumerate(nums):
        prefix[i + 1] = prefix[i] + x

     f = {}
    last = {}
    max_diff = -10**18
    best_k = 0

     for i, x in enumerate(nums):
        if x <= 1:
            continue

         # 分解出 x 的所有不同质因子
        temp = x
        factors = []
        while temp > 1:
            p = spf[temp]
            factors.append(p)
            while temp % p == 0:
                temp //= p

         for p in factors:
            prev_f = f.get(p, 0)
            prev_last = last.get(p, 0)

             diff = max(prev_f - prefix[i] + prefix[prev_last], 0) + x
            f[p] = diff

             if diff > max_diff or (diff == max_diff and p < best_k):
                max_diff = diff
                best_k = p

             last[p] = i + 1

     return max_diff * best_k % MOD

 if __name__ == '__main__':
    nums = [1, 4, 6, 8]
    print(divisible_game(nums))

C++完整代码如下：

  

  

    

using namespace std;

 constint MX = 1'000'001;
vector 
 
 int 
 >> primeDivisors(MX); 
 
 
 
 
 // 预处理每个数的质因子 
 
 
 void init() { 
 
 
      
 for 
  ( 
 int 
  i =  
 2 
 ; i < MX; ++i) { 
 
 
          
 if 
  (primeDivisors[i].empty()) {  
 // i 是质数 
 
 
              
 for 
  ( 
 int 
  j = i; j < MX; j += i) { 
 
 
                 primeDivisors[j].push_back(i);  
 // i 是 j 的质因子 
 
 
             } 
 
 
         } 
 
 
     } 
 
 
 } 
 
 
 
 
 int 
  divisibleGame(vector< 
 int 
 >& nums) { 
 
 
      
 const 
  long long MOD =  
 1 
 '000' 
 000 
 '007LL;
    int n = nums.size();
    vector 
 
 sum(n + 1, 0); 
 
    for (int i = 0; i < n; ++i) {
        sum[i + 1] = sum[i] + nums[i];
    }

     if (sum[n] == n) {
        // 每个数都是 1
        // 最优是只选一个 1（分数差为 -1），最小 k 为 2
        return (MOD - 2) % MOD;
    }

     vector 
 
 f(MX, 0); 
 
    vector 
 
 last(MX, 0); 
 
    long long maxDiff = LLONG_MIN;
    int bestK = 0;

     for (int i = 0; i < n; ++i) {
        int x = nums[i];
        if (x < 2) continue; // 没有质因子
        for (int p : primeDivisors[x]) {
            long long diff = max(f[p] - sum[i] + sum[last[p]], 0LL) + x;
            f[p] = diff;
            if (diff > maxDiff || (diff == maxDiff && p < bestK)) {
                maxDiff = diff;
                bestK = p;
            }
            last[p] = i + 1;
        }
    }

     return (maxDiff % MOD) * (bestK % MOD) % MOD;
}

 int main() {
    init();
    vector 
 
 nums = {1, 4, 6, 8}; 
 
    int result = divisibleGame(nums);
    cout << result << endl;
    return 0;
}
 
 

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。