Sum of Beautiful Subsequences
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 10^9 + 7.
Example 1
Input
nums = [1,2,3]Output
10The total beauty is
5 + 2 + 3 = 10 across GCDs 1, 2, and 3.Example 2
Input
nums = [4,6]Output
12The total beauty is
2 + 4 + 6 = 12 across GCDs 2, 4, and 6.Constraints
- 1 <= n == nums.length <= 10^4
- 1 <= nums[i] <= 7 * 10^4