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。
莫比乌斯函数μ(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 不互质的原始元素数量selectedValue = 6为例假设：
nums = [3, 4, 6]
selectedValue = 66的相关因子为：
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 = 55不存在。
所有原数都与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) = 12必须被修改。可以直接将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 - 1 = 0这个得分不会超过默认答案0，所以代码不必专门处理这种情况。
十二、示例执行过程
输入：
nums = [3, 4, 6]
maxVal = 555 <= 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 = 44数组中已经存在4。
与4不互质的元素有：
4、6选定4后，6必须被修改，修改代价为：
2 - 1 = 1得分：
4 - 1 = 3各候选值中最大得分为：
4因此输出：
4设：
•
N = len(nums)；•
M = max(nums)；•
V = max(M, maxVal)；•
MX = 100001。
代码中的倍数枚举总次数为：
MX/1 + MX/2 + MX/3 + ... + MX/MX因此时间复杂度为：
O(MX log MX)divisors对于每个i，枚举它的所有倍数，整体复杂度为：
O(MX log MX)cnt遍历一次数组：
O(N)cntMulti对每个i枚举所有倍数：
O(M log M)最多枚举V个候选值。
每个候选值会遍历它的平方因子自由因子列表。将所有候选值的因子列表长度加起来，整体为：
O(V log V)因此这一部分时间复杂度为：
O(V log V)综合起来：
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)divisors因子列表所有数的平方因子自由因子列表总长度为：
O(MX log MX)因此这部分是主要空间开销。
3.cntcntMulti
大小都与max(nums)有关：
O(M)只使用常数级额外变量：
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)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 ansif __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助力您的未来发展。
![这就是数学运算的魅力……[并不简单]](http://videoimg.ws.126.net/cover/20261012/4ASz85VLg_cover.jpg)
热门跟贴