2026-02-03：子序列美丽值求和。用go语言，给定一个长度为 n 的整数数组 nums。 对于任意正整数 g，称 g 的“
【摘要】 2026-02-03：子序列美丽值求和。用go语言，给定一个长度为 n 的整数数组 nums。对于任意正整数 g，称 g 的“价值”为：g 乘以数组中满足下列两个条件的非空子序列的个数——（1）子序列中的元素严格递增；（2）子序列所有元素的最大公约数恰好等于 g。要求计算对所有正整数 g 的这些价值之和，并将结果对 1000000007 取余后返回。备注：子序列是指从原数组中按原有相对顺序删...
2026-02-03：子序列美丽值求和。用go语言，给定一个长度为 n 的整数数组 nums。
对于任意正整数 g，称 g 的“价值”为：g 乘以数组中满足下列两个条件的非空子序列的个数——（1）子序列中的元素严格递增；（2）子序列所有元素的最大公约数恰好等于 g。要求计算对所有正整数 g 的这些价值之和，并将结果对 1000000007 取余后返回。
备注：子序列是指从原数组中按原有相对顺序删除若干（可以是零个）元素后得到的序列。
1 <= n == nums.length <= 10000。
1 <= nums[i] <= 7 × 10000。
输入：nums = [4,6]。
输出：12。
解释：
所有严格递增子序列及其 GCD 如下：
| 子序列 | GCD |
|---|---|
| [4] | 4 |
| [6] | 6 |
| [4, 6] | 2 |
计算每个 GCD 的美丽值：
| GCD | 子序列数量 | 美丽值 (GCD × 数量) |
|---|---|---|
| 2 | 1 | 2 × 1 = 2 |
| 4 | 1 | 4 × 1 = 4 |
| 6 | 1 | 6 × 1 = 6 |
美丽值总和为 2 + 4 + 6 = 12。
题目来自力扣3671。
🧩 算法步骤解析
-
预处理每个数的所有因子
- 算法首先初始化一个全局列表
divisors，用于存储1到70000之间每个数的所有因子。 - 采用一种高效的方法：对于每个数
i，将其添加到所有它的倍数j的因子列表中。这样，当需要获取一个数x的因子时，可以直接从divisors[x]中O(1)时间查到。
- 算法首先初始化一个全局列表
-
按因子将元素分组
- 遍历输入数组
nums中的每个元素x。 - 对于每个
x，查找其所有的因子d（从预处理的divisors[x]中获取）。 - 将元素
x加入到其每个因子d所对应的分组groups[d]中。最终，groups[d]包含了原数组中所有能被d整除的元素。
- 遍历输入数组
-
计算每个分组内的严格递增子序列数目
- 这一步骤是核心。算法从最大的可能因子（即数组中的最大值
m）开始，向下遍历到1。 - 对于每个因子
i，其对应的分组groups[i]包含了所有能被i整除的数。目标是计算在这个分组中，元素严格递增的子序列有多少个。 - 计算时使用了树状数组（Fenwick Tree） 结合动态规划的思想：
- 树状数组优化：为了避免对每个分组都重新初始化整个树状数组，使用了“时间戳”技术。用一个
time数组记录每个位置最后一次被更新的时间。每次计算新的分组时，递增时间戳now。当访问树状数组的某个位置时，如果其时间戳不等于当前时间戳，则视为该位置值为0。这实现了树状数组的懒重置，节省了初始化时间。 - 动态规划计数：遍历分组
groups[i]中的每个元素x。树状数组维护的是，在当前分组中，以不超过某个数值结尾的严格递增子序列的总数。对于元素x，查询所有小于x的结尾对应的子序列数目之和（通过pre(x-1)实现），这个和就是以x结尾的新的严格递增子序列数目（因为可以将x追加到这些子序列之后）。此外，x本身也构成一个子序列。将这个数目加入总和，并更新树状数组。
- 树状数组优化：为了避免对每个分组都重新初始化整个树状数组，使用了“时间戳”技术。用一个
- 这一步骤是核心。算法从最大的可能因子（即数组中的最大值
-
容斥原理处理GCD约束
- 上一步计算出的
f[i]表示的是分组groups[i]（即所有元素能被i整除）中的严格递增子序列数目。但题目要求子序列的最大公约数恰好等于i，而不仅仅是能被i整除。 - 例如，一个子序列的GCD恰好是
i，那么它必然也出现在所有i的倍数（如2i,3i等）的分组中。为了得到“恰好等于i”的子序列数目，需要使用容斥原理。 - 算法从最大的因子
i开始向下处理。对于每个i，从初步计算的f[i]中减去所有i的倍数j所对应的f[j]。即：f[i] = f[i] - f[2i] - f[3i] - ...。这样操作后，f[i]就精确代表了子序列GCD恰好为i的数目。
- 上一步计算出的
-
汇总最终结果
- 对于每个因子
i，将其精确的子序列数目f[i]乘以i本身，得到该GCD的“价值”。 - 将所有因子的价值累加，并对结果取模
1000000007，得到最终的答案。
- 对于每个因子
⏱️ 时间复杂度分析
算法的总时间复杂度由几个部分构成：
- 预处理因子：这是一个固定的开销，与输入数组无关。它遍历
1到70000之间的每个数i，并对每个i处理其倍数。这部分的时间复杂度是 O(M log M)，其中M是数值的上限（70000），这是一个调和级数求和。 - 分组元素：遍历数组
nums的每个元素n，以及每个元素的因子个数。一个数的因子个数通常远小于该数本身，平均而言可视为常数。这部分复杂度约为 O(n)。 - 计算递增子序列：这是最耗时的部分。需要处理每个分组
groups[i]。树状数组的每次查询和更新操作是 O(log M)。处理一个大小为s的分组的时间复杂度是 O(s log M)。所有分组的大小之和最大可能为 O(n * 平均因子个数)，约为 O(n)。因此，这部分的总复杂度在最坏情况下可达 O(n log M)。 - 容斥原理：遍历每个因子
i，并减去其倍数的值。对于每个i，需要处理的倍数个数约为M/i。所有i的M/i之和也是一个调和级数，复杂度为 O(M log M)。
总的时间复杂度可以概括为 O(M log M + n log M)，其中 M 是数组元素的最大可能值（70000），n 是输入数组 nums 的长度。
💾 空间复杂度分析
算法占用的额外空间主要包括：
- 因子列表
divisors：存储M个数的因子，所有因子列表的总长度也是 O(M log M)。 - 分组
groups：存储M个分组，所有分组中元素的总数最多为 O(n * 平均因子个数)，约为 O(n)。 - 树状数组及相关数组：大小为 O(M)。
- 容斥原理使用的数组
f：大小为 O(M)。
总的额外空间复杂度为 O(M log M + n + M)，简化为 O(M log M + n)。
Go完整代码如下：
package main
import (
"fmt"
"slices"
)
const mod = 1_000_000_007
const mx = 70_001
var divisors [mx][]int
func init() {
// 预处理每个数的因子
for i := 1; i < mx; i++ {
for j := i; j < mx; j += i { // 枚举 i 的倍数 j
divisors[j] = append(divisors[j], i) // i 是 j 的因子
}
}
}
func totalBeauty(nums []int) (ans int) {
m := slices.Max(nums)
// 树状数组（时间戳优化）
tree := make([]int, m+1)
time := make([]int, m+1) // 避免反复初始化树状数组
now := 0
update := func(i, val int) {
for ; i <= m; i += i & -i {
if time[i] < now {
time[i] = now
tree[i] = 0 // 懒重置
}
tree[i] += val
}
}
pre := func(i int) (res int) {
for ; i > 0; i &= i - 1 {
if time[i] == now {
res += tree[i]
}
}
return res % mod
}
// 计算 b 的严格递增子序列的个数
countIncreasingSubsequence := func(b []int) (res int) {
now++ // 重置树状数组（懒重置）
for _, x := range b {
// cnt 表示以 x 结尾的严格递增子序列的个数
cnt := pre(x-1) + 1 // +1 是因为 x 可以一个数组成一个子序列
res += cnt
update(x, cnt) // 更新以 x 结尾的严格递增子序列的个数
}
return res % mod
}
groups := make([][]int, m+1)
for _, x := range nums {
for _, d := range divisors[x] {
groups[d] = append(groups[d], x)
}
}
f := make([]int, m+1)
for i := m; i > 0; i-- {
f[i] = countIncreasingSubsequence(groups[i])
// 倍数容斥
for j := i * 2; j <= m; j += i {
f[i] -= f[j]
}
// 注意 |f[i]| * i < mod * (m / i) * i = mod * m
// m 个 mod * m 相加，至多为 mod * m * m，不会超过 64 位整数最大值
ans += f[i] * i
}
// 保证结果非负
return (ans%mod + mod) % mod
}
func main() {
nums := []int{4, 6}
result := totalBeauty(nums)
fmt.Println(result)
}
Python完整代码如下：
# -*-coding:utf-8-*-
from typing import List
import sys
MOD = 1_000_000_007
MX = 70001
# 预处理每个数的因子
divisors = [[] for _ in range(MX)]
for i in range(1, MX):
for j in range(i, MX, i):
divisors[j].append(i)
def totalBeauty(nums: List[int]) -> int:
m = max(nums)
# BIT树状数组（时间戳优化）
tree = [0] * (m + 1)
time = [0] * (m + 1) # 避免反复初始化树状数组
now = 0
def update(i: int, val: int):
while i <= m:
if time[i] < now:
time[i] = now
tree[i] = 0 # 懒重置
tree[i] += val
i += i & -i
def pre(i: int) -> int:
res = 0
while i > 0:
if time[i] == now:
res += tree[i]
i -= i & -i
return res % MOD
def countIncreasingSubsequence(b: List[int]) -> int:
nonlocal now
now += 1 # 重置树状数组（懒重置）
res = 0
for x in b:
# cnt 表示以 x 结尾的严格递增子序列的个数
cnt = pre(x - 1) + 1 # +1 是因为 x 可以一个数组成一个子序列
res = (res + cnt) % MOD
update(x, cnt) # 更新以 x 结尾的严格递增子序列的个数
return res % MOD
# 按最大公因数分组
groups = [[] for _ in range(m + 1)]
for x in nums:
for d in divisors[x]:
if d <= m:
groups[d].append(x)
f = [0] * (m + 1)
ans = 0
for i in range(m, 0, -1):
if not groups[i]:
continue
f[i] = countIncreasingSubsequence(groups[i])
# 倍数容斥
for j in range(i * 2, m + 1, i):
f[i] = (f[i] - f[j]) % MOD
ans = (ans + f[i] * i) % MOD
return (ans + MOD) % MOD
if __name__ == "__main__":
nums = [4, 6]
result = totalBeauty(nums)
print(result)
C++完整代码如下：
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
const int MOD = 1'000'000'007;
const int MX = 70'001;
vector<int> divisors[MX];
// 预处理每个数的因子
void init() {
for (int i = 1; i < MX; i++) {
for (int j = i; j < MX; j += i) {
divisors[j].push_back(i);
}
}
}
class Solution {
public:
int totalBeauty(vector<int>& nums) {
init(); // 初始化因子表
int m = *max_element(nums.begin(), nums.end());
// 树状数组（时间戳优化）
vector<int> tree(m + 1, 0);
vector<int> time(m + 1, 0); // 避免反复初始化树状数组
int now = 0;
// 更新函数
auto update = [&](int i, int val) {
while (i <= m) {
if (time[i] < now) {
time[i] = now;
tree[i] = 0; // 懒重置
}
tree[i] = (tree[i] + val) % MOD;
i += i & -i;
}
};
// 前缀和查询
auto pre = [&](int i) -> int {
int res = 0;
while (i > 0) {
if (time[i] == now) {
res = (res + tree[i]) % MOD;
}
i -= i & -i;
}
return res;
};
// 计算严格递增子序列个数
auto countIncreasingSubsequence = [&](vector<int>& b) -> int {
now++; // 重置树状数组（懒重置）
int res = 0;
for (int x : b) {
// cnt 表示以 x 结尾的严格递增子序列的个数
int cnt = (pre(x - 1) + 1) % MOD; // +1 是因为 x 可以一个数组成一个子序列
res = (res + cnt) % MOD;
update(x, cnt); // 更新以 x 结尾的严格递增子序列的个数
}
return res;
};
// 按最大公因数分组
vector<vector<int>> groups(m + 1);
for (int x : nums) {
for (int d : divisors[x]) {
if (d <= m) {
groups[d].push_back(x);
}
}
}
vector<int> f(m + 1, 0);
long long ans = 0;
for (int i = m; i > 0; i--) {
if (groups[i].empty()) continue;
f[i] = countIncreasingSubsequence(groups[i]);
// 倍数容斥
for (int j = i * 2; j <= m; j += i) {
f[i] = (f[i] - f[j]) % MOD;
}
ans = (ans + (long long)f[i] * i) % MOD;
}
return (ans % MOD + MOD) % MOD;
}
};
int main() {
vector<int> nums = {4, 6};
Solution solution;
int result = solution.totalBeauty(nums);
cout << result << endl;
return 0;
}
【声明】本内容来自华为云开发者社区博主，不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息，否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）