3671. Sum of Beautiful Subsequences
SourceWeekly Contest 465 Q4DifficultyHardRating2647
Description
You are given an integer array nums of length n.
For every positive integer g, we define the beauty of g as the product of g and the number of strictly increasing subsequences of nums whose greatest common divisor (GCD) is exactly g.
Return the sum of beauty values for all positive integers g.
Since the answer could be very large, return it modulo 109 + 7.
Example 1:
Input: nums = [1,2,3]
Output: 10
Explanation:
All strictly increasing subsequences and their GCDs are:
| Subsequence | GCD |
|---|---|
| [1] | 1 |
| [2] | 2 |
| [3] | 3 |
| [1,2] | 1 |
| [1,3] | 1 |
| [2,3] | 1 |
| [1,2,3] | 1 |
Calculating beauty for each GCD:
| GCD | Count of subsequences | Beauty (GCD × Count) |
|---|---|---|
| 1 | 5 | 1 × 5 = 5 |
| 2 | 1 | 2 × 1 = 2 |
| 3 | 1 | 3 × 1 = 3 |
Total beauty is 5 + 2 + 3 = 10.
Example 2:
Input: nums = [4,6]
Output: 12
Explanation:
All strictly increasing subsequences and their GCDs are:
| Subsequence | GCD |
|---|---|
| [4] | 4 |
| [6] | 6 |
| [4,6] | 2 |
Calculating beauty for each GCD:
| GCD | Count of subsequences | Beauty (GCD × Count) |
|---|---|---|
| 2 | 1 | 2 × 1 = 2 |
| 4 | 1 | 4 × 1 = 4 |
| 6 | 1 | 6 × 1 = 6 |
Total beauty is 2 + 4 + 6 = 12.
Constraints:
1 <= n == nums.length <= 1041 <= nums[i] <= 7 * 104
Solutions
Solution 1
Thinking
A subsequence's beauty is typically a function of its \(\gcd\). With \(n\le 10^4\) and values up to \(7\times 10^4\), count by \(\gcd=d\) and apply inclusion.
For each \(d\), run a Fenwick DP on the multiples of \(d\) to obtain \(g[d]\), the total of subsequences whose \(\gcd\) is a multiple of \(d\).
Set \(f[d]=g[d]-\sum_{t>1}f[td]\) so \(f[d]\) is the exact-\(\gcd\) contribution. The answer is \(\sum d\cdot f[d]\).
1 | |
1 | |
1 | |
1 | |