2026-02-03：子序列美丽值求和。用go语言，给定一个长度为 n 的整数数组 nums。对于任意正整数 g，称 g 的“价值”为：g 乘以数组中满足

福大大架构师每日一题

发布于 2026-02-09 14:47:15

1030

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。

🧩 算法步骤解析

1. 预处理每个数的所有因子
- • 算法首先初始化一个全局列表 divisors，用于存储 1 到 70000 之间每个数的所有因子。
- • 采用一种高效的方法：对于每个数 i，将其添加到所有它的倍数 j 的因子列表中。这样，当需要获取一个数 x 的因子时，可以直接从 divisors[x] 中O(1)时间查到。
2. 按因子将元素分组
- • 遍历输入数组 nums 中的每个元素 x。
- • 对于每个 x，查找其所有的因子 d（从预处理的 divisors[x] 中获取）。
- • 将元素 x 加入到其每个因子 d 所对应的分组 groups[d] 中。最终，groups[d] 包含了原数组中所有能被 d 整除的元素。
3. 计算每个分组内的严格递增子序列数目
- • 这一步骤是核心。算法从最大的可能因子（即数组中的最大值 m）开始，向下遍历到 1。
- • 对于每个因子 i，其对应的分组 groups[i] 包含了所有能被 i 整除的数。目标是计算在这个分组中，元素严格递增的子序列有多少个。
- • 计算时使用了树状数组（Fenwick Tree） 结合动态规划的思想：
  - • 树状数组优化：为了避免对每个分组都重新初始化整个树状数组，使用了“时间戳”技术。用一个 time 数组记录每个位置最后一次被更新的时间。每次计算新的分组时，递增时间戳 now。当访问树状数组的某个位置时，如果其时间戳不等于当前时间戳，则视为该位置值为0。这实现了树状数组的懒重置，节省了初始化时间。
  - • 动态规划计数：遍历分组 groups[i] 中的每个元素 x。树状数组维护的是，在当前分组中，以不超过某个数值结尾的严格递增子序列的总数。对于元素 x，查询所有小于 x 的结尾对应的子序列数目之和（通过 pre(x-1) 实现），这个和就是以 x 结尾的新的严格递增子序列数目（因为可以将 x 追加到这些子序列之后）。此外，x 本身也构成一个子序列。将这个数目加入总和，并更新树状数组。
4. 容斥原理处理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 的数目。
5. 汇总最终结果
- • 对于每个因子 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;

constint 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;
    return0;
}