3671. Sum of Beautiful Subsequences Hard
1/**
2 * [3671] Sum of Beautiful Subsequences
3 *
4 * You are given an integer array nums of length n.
5 * For every positive integer g, we define the beauty of g as the product of g and the number of strictly increasing <span data-keyword="subsequence-array-nonempty">subsequences</span> of nums whose greatest common divisor (GCD) is exactly g.
6 * Return the sum of beauty values for all positive integers g.
7 * Since the answer could be very large, return it modulo 10^9 + 7.
8 *
9 * <strong class="example">Example 1:
10 * <div class="example-block">
11 * Input: <span class="example-io">nums = [1,2,3]</span>
12 * Output: <span class="example-io">10</span>
13 * Explanation:
14 * All strictly increasing subsequences and their GCDs are:
15 * <table style="border: 1px solid black;">
16 * <thead>
17 * <tr>
18 * <th style="border: 1px solid black;">Subsequence</th>
19 * <th style="border: 1px solid black;">GCD</th>
20 * </tr>
21 * </thead>
22 * <tbody>
23 * <tr>
24 * <td style="border: 1px solid black;">[1]</td>
25 * <td style="border: 1px solid black;">1</td>
26 * </tr>
27 * <tr>
28 * <td style="border: 1px solid black;">[2]</td>
29 * <td style="border: 1px solid black;">2</td>
30 * </tr>
31 * <tr>
32 * <td style="border: 1px solid black;">[3]</td>
33 * <td style="border: 1px solid black;">3</td>
34 * </tr>
35 * <tr>
36 * <td style="border: 1px solid black;">[1,2]</td>
37 * <td style="border: 1px solid black;">1</td>
38 * </tr>
39 * <tr>
40 * <td style="border: 1px solid black;">[1,3]</td>
41 * <td style="border: 1px solid black;">1</td>
42 * </tr>
43 * <tr>
44 * <td style="border: 1px solid black;">[2,3]</td>
45 * <td style="border: 1px solid black;">1</td>
46 * </tr>
47 * <tr>
48 * <td style="border: 1px solid black;">[1,2,3]</td>
49 * <td style="border: 1px solid black;">1</td>
50 * </tr>
51 * </tbody>
52 * </table>
53 * Calculating beauty for each GCD:
54 * <table style="border: 1px solid black;">
55 * <thead>
56 * <tr>
57 * <th style="border: 1px solid black;">GCD</th>
58 * <th style="border: 1px solid black;">Count of subsequences</th>
59 * <th style="border: 1px solid black;">Beauty (GCD × Count)</th>
60 * </tr>
61 * </thead>
62 * <tbody>
63 * <tr>
64 * <td style="border: 1px solid black;">1</td>
65 * <td style="border: 1px solid black;">5</td>
66 * <td style="border: 1px solid black;">1 × 5 = 5</td>
67 * </tr>
68 * <tr>
69 * <td style="border: 1px solid black;">2</td>
70 * <td style="border: 1px solid black;">1</td>
71 * <td style="border: 1px solid black;">2 × 1 = 2</td>
72 * </tr>
73 * <tr>
74 * <td style="border: 1px solid black;">3</td>
75 * <td style="border: 1px solid black;">1</td>
76 * <td style="border: 1px solid black;">3 × 1 = 3</td>
77 * </tr>
78 * </tbody>
79 * </table>
80 * Total beauty is 5 + 2 + 3 = 10.
81 * </div>
82 * <strong class="example">Example 2:
83 * <div class="example-block">
84 * Input: <span class="example-io">nums = [4,6]</span>
85 * Output: <span class="example-io">12</span>
86 * Explanation:
87 * All strictly increasing subsequences and their GCDs are:
88 * <table style="border: 1px solid black;">
89 * <thead>
90 * <tr>
91 * <th style="border: 1px solid black;">Subsequence</th>
92 * <th style="border: 1px solid black;">GCD</th>
93 * </tr>
94 * </thead>
95 * <tbody>
96 * <tr>
97 * <td style="border: 1px solid black;">[4]</td>
98 * <td style="border: 1px solid black;">4</td>
99 * </tr>
100 * <tr>
101 * <td style="border: 1px solid black;">[6]</td>
102 * <td style="border: 1px solid black;">6</td>
103 * </tr>
104 * <tr>
105 * <td style="border: 1px solid black;">[4,6]</td>
106 * <td style="border: 1px solid black;">2</td>
107 * </tr>
108 * </tbody>
109 * </table>
110 * Calculating beauty for each GCD:
111 * <table style="border: 1px solid black;">
112 * <thead>
113 * <tr>
114 * <th style="border: 1px solid black;">GCD</th>
115 * <th style="border: 1px solid black;">Count of subsequences</th>
116 * <th style="border: 1px solid black;">Beauty (GCD × Count)</th>
117 * </tr>
118 * </thead>
119 * <tbody>
120 * <tr>
121 * <td style="border: 1px solid black;">2</td>
122 * <td style="border: 1px solid black;">1</td>
123 * <td style="border: 1px solid black;">2 × 1 = 2</td>
124 * </tr>
125 * <tr>
126 * <td style="border: 1px solid black;">4</td>
127 * <td style="border: 1px solid black;">1</td>
128 * <td style="border: 1px solid black;">4 × 1 = 4</td>
129 * </tr>
130 * <tr>
131 * <td style="border: 1px solid black;">6</td>
132 * <td style="border: 1px solid black;">1</td>
133 * <td style="border: 1px solid black;">6 × 1 = 6</td>
134 * </tr>
135 * </tbody>
136 * </table>
137 * Total beauty is 2 + 4 + 6 = 12.
138 * </div>
139 *
140 * Constraints:
141 *
142 * 1 <= n == nums.length <= 10^4
143 * 1 <= nums[i] <= 7 * 10^4
144 *
145 */
146pub struct Solution {}
147
148// problem: https://leetcode.com/problems/sum-of-beautiful-subsequences/
149// discuss: https://leetcode.com/problems/sum-of-beautiful-subsequences/discuss/?currentPage=1&orderBy=most_votes&query=
150
151// submission codes start here
152
153impl Solution {
154 pub fn total_beauty(nums: Vec<i32>) -> i32 {
155 0
156 }
157}
158
159// submission codes end
160
161#[cfg(test)]
162mod tests {
163 use super::*;
164
165 #[test]
166 fn test_3671() {
167 }
168}
169Back
© 2026 bowen.ge All Rights Reserved.