Hard
题目描述
给你一个长度为 n 的整数数组 nums。
对于每个正整数 g，我们定义 g 的美丽值为 g 与 nums 中最大公约数恰好等于 g 的严格递增子序列数量的乘积。
返回所有正整数 g 的美丽值之和。
由于答案可能很大，请返回对 10^9 + 7 取模的结果。
示例 1：
输入：nums = [1,2,3]
输出：10
解释：
所有严格递增子序列及其最大公约数为：
- [1] -> GCD = 1
- [2] -> GCD = 2
- [3] -> GCD = 3
- [1,2] -> GCD = 1
- [1,3] -> GCD = 1
- [2,3] -> GCD = 1
- [1,2,3] -> GCD = 1
计算每个 GCD 的美丽值：
- GCD = 1：5 个子序列，美丽值 = 1 × 5 = 5
- GCD = 2：1 个子序列，美丽值 = 2 × 1 = 2
- GCD = 3：1 个子序列，美丽值 = 3 × 1 = 3
总美丽值 = 5 + 2 + 3 = 10
示例 2：
输入：nums = [4,6]
输出：12
解释：
所有严格递增子序列及其最大公约数为：
- [4] -> GCD = 4
- [6] -> GCD = 6
- [4,6] -> GCD = 2
计算每个 GCD 的美丽值：
- GCD = 2：1 个子序列，美丽值 = 2 × 1 = 2
- GCD = 4：1 个子序列，美丽值 = 4 × 1 = 4
- GCD = 6：1 个子序列，美丽值 = 6 × 1 = 6
总美丽值 = 2 + 4 + 6 = 12
约束条件：
- 1 <= n == nums.length <= 10^4
- 1 <= nums[i] <= 7 × 10^4
解题思路
这道题要求计算所有 GCD 恰好为 g 的严格递增子序列数量，然后计算每个 g 对应的美丽值（g × 数量）。
解题思路：
GCD 处理：对于每个候选 GCD g，我们只保留能被 g 整除的元素，并将它们除以 g。这样，原数组中 GCD 为 g 的倍数的子序列，在新数组中对应 GCD 为 1 或更大值的子序列。
计算递增子序列：使用树状数组（Fenwick Tree）来高效计算严格递增子序列的数量。首先对元素进行坐标压缩，然后动态维护以某个值结尾的子序列数量。
容斥原理：直接计算得到的是 GCD 为 g 的倍数的子序列数量。要得到 GCD 恰好为 g 的数量，需要减去 GCD 为 g 的倍数（如 2g、3g 等）的数量。
从大到小处理：为了正确应用容斥原理，我们从最大的 GCD 开始向下处理，确保处理 g 时，所有 g 的倍数都已经处理完毕。
算法步骤：
- 遍历所有可能的 GCD 值 g
- 对于每个 g，提取能被 g 整除的元素并缩放
- 使用树状数组计算严格递增子序列数量
- 应用容斥原理得到 GCD 恰好为 g 的子序列数量
- 累加所有 g × count[g] 得到最终答案
代码实现
class Solution {
public:
int totalBeauty(vector<int>& nums) {
const int MOD = 1e9 + 7;
int maxVal = *max_element(nums.begin(), nums.end());
vector<long long> cnt(maxVal + 1);
// 计算每个GCD对应的子序列数量（包含倍数）
for (int g = 1; g <= maxVal; g++) {
vector<int> divisible;
for (int num : nums) {
if (num % g == 0) {
divisible.push_back(num / g);
}
}
if (divisible.empty()) continue;
// 坐标压缩
vector<int> sorted = divisible;
sort(sorted.begin(), sorted.end());
sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
int n = sorted.size();
vector<long long> dp(n + 1);
// 计算严格递增子序列数量
for (int x : divisible) {
int pos = lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin() + 1;
long long ways = 1; // 单个元素构成的子序列
// 计算以x结尾的子序列数量
for (int i = 1; i < pos; i++) {
ways = (ways + dp[i]) % MOD;
}
dp[pos] = (dp[pos] + ways) % MOD;
}
// 统计总数量
for (int i = 1; i <= n; i++) {
cnt[g] = (cnt[g] + dp[i]) % MOD;
}
}
// 容斥原理：从大到小处理，减去倍数的贡献
vector<long long> exact(maxVal + 1);
for (int g = maxVal; g >= 1; g--) {
exact[g] = cnt[g];
for (int k = 2 * g; k <= maxVal; k += g) {
exact[g] = (exact[g] - exact[k] + MOD) % MOD;
}
}
// 计算最终答案
long long result = 0;
for (int g = 1; g <= maxVal; g++) {
result = (result + (long long)g * exact[g]) % MOD;
}
return result;
}
};
class Solution:
def totalBeauty(self, nums: List[int]) -> int:
MOD = 10**9 + 7
max_val = max(nums)
cnt = [0] * (max_val + 1)
# 计算每个GCD对应的子序列数量（包含倍数）
for g in range(1, max_val + 1):
divisible = [num // g for num in nums if num % g == 0]
if not divisible:
continue
# 坐标压缩
sorted_vals = sorted(set(divisible))
val_to_idx = {v: i for i, v in enumerate(sorted_vals)}
n = len(sorted_vals)
# 计算严格递增子序列数量
dp = [0] * (n + 1)
for x in divisible:
pos = val_to_idx[x] + 1
ways = 1 # 单个元素构成的子序列
# 计算以x结尾的子序列数量
for i in range(1, pos):
ways = (ways + dp[i]) % MOD
dp[pos] = (dp[pos] + ways) % MOD
# 统计总数量
cnt[g] = sum(dp[1:]) % MOD
# 容斥原理：从大到小处理，减去倍数的贡献
exact = [0] * (max_val + 1)
for g in range(max_val, 0, -1):
exact[g] = cnt[g]
for k in range(2 * g, max_val + 1, g):
exact[g] = (exact[g] - exact[k]) % MOD
# 计算最终答案
result = 0
for g in range(1, max_val + 1):
result = (result + g * exact[g]) % MOD
return result
public class Solution {
public int TotalBeauty(int[] nums) {
const int MOD = 1000000007;
int maxVal = nums.Max();
long[] cnt = new long[maxVal + 1];
// 计算每个GCD对应的子序列数量（包含倍数）
for (int g = 1; g <= maxVal; g++) {
List<int> divisible = new List<int>();
foreach (int num in nums) {
if (num % g == 0) {
divisible.Add(num / g);
}
}
if (divisible.Count == 0) continue;
// 坐标压缩
List<int> sorted = divisible.Distinct().OrderBy(x => x).ToList();
Dictionary<int, int> valToIdx = new Dictionary<int, int>();
for (int i = 0; i < sorted.Count; i++) {
valToIdx[sorted[i]] = i;
}
int n = sorted.Count;
long[] dp = new long[n + 1];
// 计算严格递增子序列数量
foreach (int x in divisible) {
int pos = valToIdx[x] + 1;
long ways = 1; // 单个元素构成的子序列
// 计算以x结尾的子序列数量
for (int i = 1; i < pos; i++) {
ways = (ways + dp[i]) % MOD;
}
dp[pos] = (dp[pos] + ways) % MOD;
}
// 统计总数量
for (int i = 1; i <= n; i++) {
cnt[g] = (cnt[g] + dp[i]) % MOD;
}
}
// 容斥原理：从大到小处理，减去倍数的贡献
long[] exact = new long[maxVal + 1];
for (int g = maxVal; g >= 1; g--) {
exact[g] = cnt[g];
for (int k = 2 * g; k <= maxVal; k += g) {
exact[g] = (exact[g] - exact[k] + MOD) % MOD;
}
}
// 计算最终答案
long result = 0;
for (int g = 1; g <= maxVal; g++) {
result = (result + (long)g * exact[g]) % MOD;
}
return (int)result;
}
}
var totalBeauty = function(nums) {
const MOD = 1000000007;
const n = nums.length;
const maxVal = Math.max(...nums);
// dp[i][g] = number of strictly increasing subsequences ending at index i with GCD g
const dp = Array(n).fill(null).map(() => new Map());
// Initialize first element
dp[0].set(nums[0], 1);
// Fill dp table
for (let i = 1; i < n; i++) {
// Single element subsequence
dp[i].set(nums[i], 1);
// Extend previous subsequences
for (let j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
for (const [gcd, count] of dp[j]) {
const newGcd = gcdFunc(gcd, nums[i]);
dp[i].set(newGcd, (dp[i].get(newGcd) || 0) + count);
}
}
}
// Apply modulo
for (const [gcd, count] of dp[i]) {
dp[i].set(gcd, count % MOD);
}
}
// Count total subsequences for each GCD
const gcdCount = new Map();
for (let i = 0; i < n; i++) {
for (const [gcd, count] of dp[i]) {
gcdCount.set(gcd, (gcdCount.get(gcd) || 0) + count);
}
}
// Calculate total beauty
let result = 0;
for (const [gcd, count] of gcdCount) {
result = (result + (gcd * (count % MOD)) % MOD) % MOD;
}
return result;
};
function gcdFunc(a, b) {
while (b !== 0) {
const temp = b;
b = a % b;
a = temp;
}
return a;
}
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(V × N × log(V)) | V 是最大值，N 是数组长度，对每个 GCD 值处理子序列计算 |
| 空间复杂度 | O(V + N) | 存储 GCD 计数和压缩后的数组 |