2026-09-12：互质元素的最大得分。用go语言，有一个长度为 n 的整数序列 nums，另外给定一个上限 maxVal。对于序列中的任意位置，都可以|下标|spiderlinebreak

分享至

2026-09-12：互质元素的最大得分。用go语言，有一个长度为 n 的整数序列 nums，另外给定一个上限 maxVal。对于序列中的任意位置，都可以把它改成 1 到 maxVal 之间的某个正整数；每改动一个位置，代价增加 1。

完成所有改动后，必须选定一个位置 i。要求改动后的 nums[i] 与序列中其他每一个位置上的数都互质，也就是它们两两之间的最大公约数都为 1。注意，只需要 nums[i] 和其他每个数互质，不要求其他数之间也互质。

设 selectedValue 为选定位置 i 最终保留下来的那个数，设 modificationCost 为总共被改动过的位置数量。得分为 selectedValue 减去 modificationCost。

目标是求出所有可行改动和选择方案中，能够得到的最大得分。

解释：

初始时，下标 1 和 3 包含标记。

将标记从下标 3 移动到下标 2。

将标记从下标 1 移动到下标 0。

被覆盖的下标为 [0, 2]，所以总值为 nums[0] + nums[2]。

1 <= nums.length <= 100000。

1 <= nums[i] <= 100000。

1 <= maxVal <= 100000。

输入： nums = [3,4,6], maxVal = 5。

输出： 4。

解释：

将 nums[2] 从 6 更改为 5，代价为 1。选择 nums[2] = 5，因为它与 3 和 4 互质。

selectedValue = 5

modificationCost = 1

得分为 5 - 1 = 4。

题目来自力扣3953。

一、代码整体思路

代码的核心做法是：

1. 枚举最终想要选择的数selectedValue；
2. 计算序列中有多少个数与它不互质；
3. 这些不互质的位置必须被修改；
4. 根据是否已经存在一个值等于selectedValue的位置，计算最少修改次数；
5. 用

selectedValue - modificationCost

更新答案。

困难在于：

如何快速统计序列中有多少个数与某个 selectedValue 不互质？

代码利用：

• 莫比乌斯函数；
• 容斥原理；
• 预处理每个数的倍数出现次数。

二、全局变量和预处理范围

const MX = 100_001

题目中：

nums[i] <= 100000
maxVal <= 100000

所以所有可能出现的数都小于MX。

代码中定义：

var mu = [MX]int{1: 1}
var divisors = [MX][]int{}

含义如下：

•mu[x]：莫比乌斯函数μ(x)；
•divisors[x]：x的所有满足μ[d] != 0的因子，并且不包含因子1。

三、预处理莫比乌斯函数 1. 莫比乌斯函数的性质

莫比乌斯函数μ(n)定义为：

•μ(1) = 1；
• 如果n含有平方因子，则μ(n) = 0；
• 如果n是k个不同质数的乘积，则：

μ(n) = (-1)^k

例如：

μ(1) = 1
μ(2) = -1
μ(3) = -1
μ(6) = 1
μ(4) = 0
μ(12) = 0

因为4和12都含有平方因子。

2. 使用的递推关系

代码利用了：

当 n > 1 时：


 ∑ μ(d) = 0
其中 d 遍历 n 的所有因子

因此：

μ(n) = - ∑ μ(d)

其中d遍历n的所有真因子。

代码：

for i := 1; i < MX; i++ {
    for j := i * 2; j < MX; j += i {
        mu[j] -= mu[i]
    }
}

处理过程可以理解为：

• 当前已知μ[i]；
• 对所有i的倍数j，把-μ[i]累加到μ[j]；
• 最后得到每个数的莫比乌斯函数值。

例如处理6时，会受到因子1、2、3的影响：

μ(6) = -[μ(1) + μ(2) + μ(3)]
     = -[1 + (-1) + (-1)]
     = 1

四、预处理平方因子自由的因子列表

代码：

for i := 2; i < MX; i++ {
    if mu[i] == 0 {
        continue
    }
    for j := i; j < MX; j += i {
        divisors[j] = append(divisors[j], i)
    }
}

这里把所有满足：

μ[i] != 0

的i加入其倍数的因子列表。

因为：

•μ[i] != 0表示i不含平方因子；
• 这些因子才需要参与莫比乌斯容斥计算；
• 因子1不需要加入，因为代码只统计与selectedValue不互质的数，1不会造成影响。

例如：

divisors[6] = [2, 3, 6]

因为：

μ(2) = -1
μ(3) = -1
μ(6) = 1

而1被故意排除。

对于：

divisors[12]

其中有效因子主要是：

2、3、6

像4、12这种含平方因子的因子，其莫比乌斯函数为0，不会加入。

五、统计每个数出现的次数

在maxScore中：

maxNum := slices.Max(nums)
cnt := make([]int, maxNum+1)
for _, x := range nums {
    cnt[x]++
}

cnt[x]表示：

nums 中等于 x 的元素个数

例如：

nums = [3, 4, 6]

则：

cnt[3] = 1
cnt[4] = 1
cnt[6] = 1

其他位置为0。

六、预处理每个数的倍数出现次数

代码：

cntMulti := make([]int, maxNum+1)
for i := 2; i <= maxNum; i++ {
    for j := i; j <= maxNum; j += i {
        cntMulti[i] += cnt[j]
    }
}

cntMulti[i]表示：

nums 中有多少个数是 i 的倍数

也就是统计：

nums 中有多少个元素 x 满足 i | x

例如：

nums = [3, 4, 6]

则：

cntMulti[2] = 2

因为4和6是2的倍数。

cntMulti[3] = 2

因为3和6是3的倍数。

cntMulti[6] = 1

因为只有6是6的倍数。

七、为什么需要莫比乌斯容斥

现在固定一个候选值：

selectedValue = x

需要统计序列中有多少个数a与x不互质。

也就是统计：

gcd(a, x) > 1

如果a和x有公共质因子，那么它们不互质。

直接对每个a计算最大公约数会比较慢。代码使用莫比乌斯容斥快速统计。

1. 统计与 x 不互质的元素数量

对于任意一个数a：

a 与 x 不互质

等价于：

gcd(a, x) > 1

根据莫比乌斯函数，有：

是否 gcd(a, x) > 1
=
∑ -μ(d)

其中d遍历：

d | x
d | a
d > 1

也就是说，d必须同时是a和x的因子。

对于固定的d：

cntMulti[d]

正好表示nums中有多少个元素是d的倍数。

因此，与x不互质的元素总数为：

∑ -μ(d) * cntMulti[d]

其中d遍历x的所有大于1的平方因子自由因子。

代码：

cost := 0
for _, d := range divisors[selectedValue] {
    if d > maxNum {
        break
    }
    cost -= mu[d] * cntMulti[d]
}

此时的cost暂时表示：

与 selectedValue 不互质的原始元素数量

2. 以selectedValue = 6为例

假设：

nums = [3, 4, 6]
selectedValue = 6

6的相关因子为：

2、3、6

对应的莫比乌斯函数值为：

μ(2) = -1
μ(3) = -1
μ(6) = 1

计算结果：

cost
= -μ(2) * cntMulti[2]
  -μ(3) * cntMulti[3]
  -μ(6) * cntMulti[6]

 = -(-1) * 2
  -(-1) * 2
  -(1) * 1

 = 2 + 2 - 1
= 3

确实，3、4、6都与6不互质：

gcd(3, 6) = 3
gcd(4, 6) = 2
gcd(6, 6) = 6

所以共有3个位置不满足要求。

八、如何计算最少修改次数

这是代码最关键的部分。

假设当前候选值是：

selectedValue = x

先设：

badCount = 与 x 不互质的原始元素数量

所有与x不互质的位置都不能保持原值，否则最终条件不满足。

但是，某些位置可以被选为目标位置并保留或改成x，因此需要分别讨论。

情况一：序列中已经存在

代码：

if selectedValue <= maxNum && cnt[selectedValue] > 0 {
    cost--
}

如果原序列中已经存在一个值等于x，那么可以选择这个位置作为最终选中的位置。

这个位置虽然满足：

gcd(x, x) = x

通常不等于1，因此它会被统计进“不互质元素数量”。

但它恰好就是我们要选择的位置，不需要修改它，也不应该因为它自身与x不互质而付出修改代价。

所以：

实际修改代价 = badCount - 1

例如：

nums = [3, 4, 6]
x = 6

共有三个数与6不互质：

3、4、6

其中6自己可以作为选定位置保留，因此只需要修改：

3 和 4

修改代价为：

3 - 1 = 2

最终可以把3、4改为1，得到：

[1, 1, 6]

此时6和其他数都互质。

得分：

6 - 2 = 4

情况二：序列中不存在，但存在不互质的元素

如果：

cnt[x] == 0

说明没有位置原本就是x。

此时需要从某个位置中选一个，修改为x，作为最终选定位置。

如果原序列中有一些元素与x不互质，那么可以从这些必须修改的位置中挑一个，直接修改成x。

因此：

• 这个位置本来就必须修改；
• 改成x与改成1的修改代价相同；
• 不需要额外增加修改次数。

所以，当：

badCount > 0

时，最小修改代价仍然是：

badCount

代码中没有额外增加1，正是这个原因。

例如：

nums = [3, 4, 6]
x = 5

5不存在。

所有原数都与5互质：

gcd(3, 5) = 1
gcd(4, 5) = 1
gcd(6, 5) = 1

所以badCount = 0，这属于下一种情况。

如果某个候选值x不存在，但有一些元素与它不互质，例如：

nums = [2, 3]
x = 4

则：

gcd(2, 4) = 2
gcd(3, 4) = 1

2必须被修改。可以直接将2改为4，并选择该位置。

因此只需要修改一个位置，而不是先把2改成1，再额外修改某个位置为4。

情况三：序列中不存在，且所有元素都与互质

代码：

else if cost == 0 {
    cost = 1
}

如果：

cnt[x] == 0
badCount == 0

• 当前所有位置都可以保持原值；
• 但是序列中没有任何位置的值是x；
• 必须至少修改一个位置，把它变成x，才能选择x作为selectedValue。

因此需要额外修改一次：

cost = 1

例如：

nums = [3, 4, 6]
x = 5

所有数都与5互质，但5不存在。

可以将6修改成5：

[3, 4, 5]

修改次数为1，得分为：

5 - 1 = 4

九、候选值的可行范围

代码的循环是：

for selectedValue := max(maxNum, maxVal); selectedValue > ans; selectedValue-- {

候选值最大为：

max(maxNum, maxVal)

原因如下。

1. 如果selectedValue <= maxVal

可以通过修改某个位置，把它变成selectedValue。

因此所有1 ~ maxVal之间的数都可能成为最终选定值。

2. 如果selectedValue > maxVal

不能通过修改得到，因为修改后的值必须不超过maxVal。

但如果原数组中本来就存在这个值，则可以不修改它，直接选择它。

代码：

if selectedValue > maxVal && cnt[selectedValue] == 0 {
    continue
}

表示：

• 如果候选值超过maxVal；
• 并且原数组中没有这个值；
• 那么它不可能成为最终选定值，直接跳过。

因此，代码既考虑了：

• 可以通过修改得到的值；
• 也考虑了原数组中已经存在、但大于maxVal的值。

十、为什么可以从大到小枚举

代码从较大的候选值开始尝试：

for selectedValue := max(maxNum, maxVal); selectedValue > ans; selectedValue-- {

得分为：

selectedValue - modificationCost

由于修改代价一定满足：

modificationCost >= 0

所以：

得分 <= selectedValue

如果当前：

selectedValue <= ans

那么即使修改代价为0，最多也只能得到：

selectedValue <= ans

不可能超过当前答案。

因此可以直接结束循环。

代码中对应的注释是：

// 如果 selectedValue <= ans，那么 ans 不会变大，跳出循环

这种剪枝不会影响正确性。

十一、selectedValue = 1的处理

代码：

if cnt[1] > 0 {
    ans = 1
}

如果原数组中已经存在1，可以直接选择这个位置：

• 不需要修改；
•1与任何正整数都互质；
• 得分为1。

因此初始答案可以设置为：

如果原数组中没有1，也可以通过修改某个位置得到1，但需要付出一次修改代价：

1 - 1 = 0

这个得分不会超过默认答案0，所以代码不必专门处理这种情况。

十二、示例执行过程

输入：

nums = [3, 4, 6]
maxVal = 5

1. 候选值5

5 <= maxVal，所以可以通过修改得到5。

原数组中：

3、4、6

都与5互质：

gcd(3, 5) = 1
gcd(4, 5) = 1
gcd(6, 5) = 1

因此：

badCount = 0

但是数组中没有5，所以必须修改一个位置得到5：

modificationCost = 1

得分：

5 - 1 = 4

例如：

[3, 4, 6] -> [3, 4, 5]

选择5，它与3、4都互质。

2. 候选值6

6 > maxVal，但是数组中已经存在6，所以可以选择它。

与6不互质的元素有：

3、4、6

其中6自己可以作为选定位置，不需要修改，因此：

modificationCost = 3 - 1 = 2

可以修改：

3 -> 1
4 -> 1

得到：

[1, 1, 6]

得分：

6 - 2 = 4

3. 候选值4

数组中已经存在4。

与4不互质的元素有：

4、6

选定4后，6必须被修改，修改代价为：

2 - 1 = 1

得分：

4 - 1 = 3

4. 最终答案

各候选值中最大得分为：

因此输出：

十三、时间复杂度

设：

•N = len(nums)；
•M = max(nums)；
•V = max(M, maxVal)；
•MX = 100001。

1. 莫比乌斯函数预处理

代码中的倍数枚举总次数为：

MX/1 + MX/2 + MX/3 + ... + MX/MX

因此时间复杂度为：

O(MX log MX)

2. 预处理divisors

对于每个i，枚举它的所有倍数，整体复杂度为：

O(MX log MX)

3. 统计cnt

遍历一次数组：

O(N)

4. 预处理cntMulti

对每个i枚举所有倍数：

O(M log M)

5. 枚举所有候选值

最多枚举V个候选值。

每个候选值会遍历它的平方因子自由因子列表。将所有候选值的因子列表长度加起来，整体为：

O(V log V)

因此这一部分时间复杂度为：

O(V log V)

6. 总时间复杂度

综合起来：

O(MX log MX + N + M log M + V log V)

由于题目中：

M <= 100000
V <= 100000
MX = 100001

所以可以简化为：

O(N + MX log MX)

如果把MX视为题目给定的固定常数，也可以写成：

O(N + 100000 log 100000)

十四、额外空间复杂度

代码使用了以下额外空间：

1. 莫比乌斯函数数组

mu

大小为MX：

O(MX)

2.divisors因子列表

所有数的平方因子自由因子列表总长度为：

O(MX log MX)

因此这部分是主要空间开销。

3.cntcntMulti

大小都与max(nums)有关：

O(M)

4. 其他变量

只使用常数级额外变量：

O(1)

总额外空间复杂度

综合来看：

O(MX log MX + M)

由于MX大于等于M，可以简化为：

O(MX log MX)

在题目给定上限下：

O(100000 log 100000)

如果只考虑函数maxScore内部、忽略全局预处理的mu和divisors，则内部额外空间是：

O(M)

但从整段程序的总额外空间来看，应当计入全局预处理数组，因此答案是：

总时间复杂度：O(N + MX log MX)
总额外空间复杂度：O(MX log MX)

Go完整代码如下：

package main

 import (
    "fmt"
    "slices"
)

 const MX = 100_001

 var mu = [MX]int{1: 1}     // 莫比乌斯函数
var divisors = [MX][]int{} // 不含平方因子的因子列表，用于容斥

 func init() {
    // 预处理莫比乌斯函数
    // 当 n > 1 时，sum_{d|n} mu[d] = 0
    // 所以 mu[n] = -sum_{d|n ∧ d 
 
    for i := 1; i < MX; i++ {
        for j := i * 2; j < MX; j += i {
            mu[j] -= mu[i] // i 是 j 的真因子
        }
    }

     // 预处理不含平方因子的因子列表
    // 本题不需要因子 1
    for i := 2; i < MX; i++ {
        if mu[i] == 0 {
            continue
        }
        for j := i; j < MX; j += i {
            divisors[j] = append(divisors[j], i) // i 是 j 的因子，且 mu[i] != 0
        }
    }
}

 func maxScore(nums []int, maxVal int) (ans int) {
    maxNum := slices.Max(nums)
    cnt := make([]int, maxNum+1)
    for _, x := range nums {
        cnt[x]++
    }
    cntMulti := make([]int, maxNum+1)
    for i := 2; i <= maxNum; i++ {
        for j := i; j <= maxNum; j += i {
            cntMulti[i] += cnt[j] // 统计 nums 中有多少个数是 i 的倍数
        }
    }

     if cnt[1] > 0 {
        ans = 1 // selectedValue = 1 时，无需修改，得分为 1
    }

     // 从大到小枚举 selectedValue
    // 优化：如果 selectedValue <= ans，那么 ans 不会变大，跳出循环
    for selectedValue := max(maxNum, maxVal); selectedValue > ans; selectedValue-- {
        if selectedValue > maxVal && cnt[selectedValue] == 0 {
            continue // 无法改成 selectedValue
        }

         // 与 selectedValue 不互质的数，其中一个数改成 selectedValue，其余数都改成 1
        cost := 0
        for _, d := range divisors[selectedValue] {
            if d > maxNum {
                break
            }
            cost -= mu[d] * cntMulti[d]
        }

         if selectedValue <= maxNum && cnt[selectedValue] > 0 {
            cost-- // 如果某个 nums[i] 恰好等于 selectedValue，可以少改一次
        } else if cost == 0 {
            cost = 1 // 至少要有一个数改成 selectedValue
        }

         ans = max(ans, selectedValue-cost)
    }

     return
}

 func main() {
    nums := []int{3, 4, 6}
    maxVal := 5
    result := maxScore(nums, maxVal)
    fmt.Println(result)
}

Python完整代码如下：

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

 MX = 100_001

 mu = [0] * MX
mu[1] = 1
divisors = [[] for _ in range(MX)]

 def init():
    # 预处理莫比乌斯函数
    for i in range(1, MX):
        for j in range(i * 2, MX, i):
            mu[j] -= mu[i]

     # 预处理不含平方因子的因子列表，不需要因子 1
    for i in range(2, MX):
        if mu[i] == 0:
            continue
        for j in range(i, MX, i):
            divisors[j].append(i)

 init()

 def maxScore(nums, maxVal):
    maxNum = max(nums)

     cnt = [0] * (maxNum + 1)
    for x in nums:
        cnt[x] += 1

     cntMulti = [0] * (maxNum + 1)
    for i in range(2, maxNum + 1):
        for j in range(i, maxNum + 1, i):
            cntMulti[i] += cnt[j]

     ans = 0
    if cnt[1] > 0:
        ans = 1

     selectedValue = max(maxNum, maxVal)
    while selectedValue > ans:
        if selectedValue > maxVal and cnt[selectedValue] == 0:
            selectedValue -= 1
            continue

         cost = 0
        for d in divisors[selectedValue]:
            if d > maxNum:
                break
            cost -= mu[d] * cntMulti[d]

         if selectedValue <= maxNum and cnt[selectedValue] > 0:
            cost -= 1
        elif cost == 0:
            cost = 1

         ans = max(ans, selectedValue - cost)
        selectedValue -= 1

     return ans

 if __name__ == "__main__":
    nums = [3, 4, 6]
    maxVal = 5
    result = maxScore(nums, maxVal)
    print(result)

C++完整代码如下：

#include  

#include  

#include  


 using namespace std;

 const int MX = 100001;

 int mu[MX];
vector divisors[MX];

 void init() {
    // 初始化莫比乌斯函数
    fill(mu, mu + MX, 0);
    mu[1] = 1;

     // 计算莫比乌斯函数
    for (int i = 1; i < MX; i++) {
        for (int j = i * 2; j < MX; j += i) {
            mu[j] -= mu[i];
        }
    }

     // 预处理不含平方因子的因子列表（不包含 1）
    for (int i = 2; i < MX; i++) {
        if (mu[i] == 0) continue;
        for (int j = i; j < MX; j += i) {
            divisors[j].push_back(i);
        }
    }
}

 int maxScore(vector& nums, int maxVal) {
    int maxNum = *max_element(nums.begin(), nums.end());

     vector cnt(maxNum + 1, 0);
    for (int x : nums) {
        cnt[x]++;
    }

     vector cntMulti(maxNum + 1, 0);
    for (int i = 2; i <= maxNum; i++) {
        for (int j = i; j <= maxNum; j += i) {
            cntMulti[i] += cnt[j];
        }
    }

     int ans = 0;
    if (cnt[1] > 0) {
        ans = 1;
    }

     int selectedValue = max(maxNum, maxVal);
    for (; selectedValue > ans; selectedValue--) {
        // 如果 selectedValue 超过 maxVal 且原数组中不存在该值，则无法选择
        if (selectedValue > maxVal && selectedValue <= maxNum && cnt[selectedValue] == 0) {
            continue;
        }

         int cost = 0;
        // 计算与 selectedValue 不互质的元素个数
        if (selectedValue < MX) {
            for (int d : divisors[selectedValue]) {
                if (d > maxNum) break;
                cost -= mu[d] * cntMulti[d];
            }
        }

         if (selectedValue <= maxNum && cnt[selectedValue] > 0) {
            cost--; // 自身不需要修改
        } else if (cost == 0) {
            cost = 1; // 至少需要将一个元素改成 selectedValue
        }

         ans = max(ans, selectedValue - cost);
    }

     return ans;
}

 int main() {
    init();

     vector nums = {3, 4, 6};
    int maxVal = 5;
    int result = maxScore(nums, maxVal);
    cout << result << endl;

     return 0;
}

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

特别声明：以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布，本平台仅提供信息存储服务。

Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.