3671. 子序列美丽值求和

难度：困难

问题描述：

给你一个长度为 n 的整数数组 nums。

对于每个 正整数 g，定义 g 的 美丽值 为 g 与 nums 中符合要求的子序列数量的乘积，子序列需要 严格递增 且最大公约数（GCD）恰好为 g 。

请返回所有正整数 g 的 美丽值 之和。

由于答案可能非常大，请返回结果对 109 + 7 取模后的值。

子序列 是一个 非空 数组，可以通过从另一个数组中删除某些元素（或不删除任何元素）而保持剩余元素顺序不变得到。

示例 1：

输入：nums = [1,2,3]

输出：10

解释：

所有严格递增子序列及其 GCD 如下：

子序列 GCD

[1]     1

[2]     2

[3]     3

[1,2]     1

[1,3]     1

[2,3]     1

[1,2,3] 1

计算每个 GCD 的美丽值：

GCD 子序列数量 美丽值 (GCD × 数量)

1   5          1 × 5 = 5

2   1          2 × 1 = 2

3   1          3 × 1 = 3

美丽值总和为 5 + 2 + 3 = 10。

示例 2：

输入：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。

提示：

1 <= n == nums.length <= 104

1 <= nums[i] <= 7 × 104

问题分析：

解决这个问题需要分别解决以下子问题：

1. 如何生成一个列表的所有子序列
2. 如何求一个子序列的gcd值
3. 对gcd值进行分类统计，相同的gcd值数量有多少个
4. 根据gcd值以及其数量计算美丽值总和

生成一个列表的所有子序列，可以这样处理，对于有n个元素的列表，我们把包含一个元素、两个元素、......、n-1个元素的子序列依次分别找出，最后再加上列表本身，就可以构成所有的子序列。为此设计函数get_one_from_nlist(a)，其功能是对有n个元素的列表去掉一个元素，返回生成的子序列的列表，这个列表中的元素应该就是有n-1个元素的子序列，如果继续对这子序列列表中的每个元素进行再去掉一个元素的处理，就可以得到n-2个元素的子序列列表，依此方法处理，就可以得到所的子序列。

求一个子序列的gcd值，方法是先计算最前面两个元素的gcd值，然后把剩下元素与生成的gcd值构成一个新的列表，再进行相同的处理，直到序列中的元素只有一个的时候，那么这个元素就是这个子序列的gcd值。这通过函数get_gcd_from_array(a)实现。

函数get_all_sub_array_gcd(a)对所有子序列进行gcd值计算，并按gcd值进行分类统计，以方便计算美丽值之和。

最后在主程序中根据按gcd值分类统计的情况计算美丽值之和并输出。

程序如下：

import math
#返回在列表a中去掉一个元素生成的子序列
def get_one_from_nlist(a):n=len(a)b=[]for i in range(n):t=a[:i]+a[i+1:]b.append(t)return b#返回在列表a中去掉k个元素生成的子序列
def get_k_from_nlist(k,a):# b=[]n=len(a)t=n-kc=[a]while t>0:b=[]for i in c:d=get_one_from_nlist(i)# print(d)for j in d:if j in b:continueelse:b.append(j)c=b[::]t=t-1c.sort()return c#返回列表a的所有子序列
def get_all_sub_array(a):n=len(a)b=[]for i in range(1,n):t=get_k_from_nlist(i,a)b.extend(t)b.append(a)b.sort(key=lambda x:(len(x)))return b#返回列表a中所有整数的GCD
def get_gcd_from_array(a):n=len(a)while n!=1:t=math.gcd(a[0],a[1])b=a[2:]b.append(t)a=bn=len(a)return a[0]#计算并返回所有子序列的gcd值
def get_all_sub_array_gcd(a):b=[]for i in a:t=get_gcd_from_array(i)print(f'子序列：{i},对应的gcd：{t}')b.append(t)c=set(b)d=[]for i in c:print(f'gcd值为{i}的数量有{b.count(i)}个')d.append([i,b.count(i)])return d#主程序
a=eval(input('pls input a='))
#计算列表的所有子序列
sub_array=get_all_sub_array(a)
#计算列表所有子序列的gcd值并按gcd值进行统计
b=get_all_sub_array_gcd(sub_array)
#计算子序列美丽值的和
s=0
for i in b:s=s+i[0]*i[1]
s=s%(10**9+7)
print(f'子序列美丽值之和为：{s}')

运行实例一

pls input a=[2,3,4]

子序列：[2],对应的gcd：2

子序列：[3],对应的gcd：3

子序列：[4],对应的gcd：4

子序列：[2, 3],对应的gcd：1

子序列：[2, 4],对应的gcd：2

子序列：[3, 4],对应的gcd：1

子序列：[2, 3, 4],对应的gcd：1

gcd值为1的数量有3个

gcd值为2的数量有2个

gcd值为3的数量有1个

gcd值为4的数量有1个

子序列美丽值之和为：14

运行实例二

pls input a=[4,8]

子序列：[4],对应的gcd：4

子序列：[8],对应的gcd：8

子序列：[4, 8],对应的gcd：4

gcd值为8的数量有1个

gcd值为4的数量有2个

子序列美丽值之和为：16

运行实例三

pls input a=[5,10,3,9]

子序列：[3],对应的gcd：3

子序列：[5],对应的gcd：5

子序列：[9],对应的gcd：9

子序列：[10],对应的gcd：10

子序列：[3, 9],对应的gcd：3

子序列：[5, 3],对应的gcd：1

子序列：[5, 9],对应的gcd：1

子序列：[5, 10],对应的gcd：5

子序列：[10, 3],对应的gcd：1

子序列：[10, 9],对应的gcd：1

子序列：[5, 3, 9],对应的gcd：1

子序列：[5, 10, 3],对应的gcd：1

子序列：[5, 10, 9],对应的gcd：1

子序列：[10, 3, 9],对应的gcd：1

子序列：[5, 10, 3, 9],对应的gcd：1

gcd值为1的数量有9个

gcd值为3的数量有2个

gcd值为5的数量有2个

gcd值为9的数量有1个

gcd值为10的数量有1个

子序列美丽值之和为：44

精心分析，抽取功能，设计函数，协调配合，完成求解。