携程 质因子个数 100%
题目就是给N个数，把这些数各种组合，可以得到一个新的数，然后新的数的不同质因子个数就是权重，问所有权重之和是多少
看样例：
3个数，1 2 6
1，没有质因子，权重0
2，质因子2，权重1
6，质因子2 3，权重2
1*2，质因子2，权重1
1*6，质因子2 3，权重2
2*6，质因子2 3，权重2
1*2*6，质因子2 3，权重2
所有总的权重为10，输出答案10
分析：
首先肯定要分解质因子，
比如6 9 15 17这4个数
6分解成2*3，我们先看2做的贡献：
6本身一次2，
6*9有一次2，6*15有一次，6*17有一次，
6*9*15有一次，6*9*17有一次，6*15*17有一次
6*9*15*17有一次
综上，一共获得了8个权重
那么看到规律，其实就是从剩下的n-1个数里拿0个来和6匹配，拿1个来和6匹配，拿2个来个6匹配，拿3个和6匹配，得出公式 C(n-1, 0) + C(n-1, 1) + C(n-1, 2) + C(n-1, 3) + ... + C(n-1, n-1)
上面的公式就是高中数学里的，化简为2^(n-1). 咱们有4个数，就是2^3=8
到这里咱们就可以计算出每个质因子的权重了，看起来分别都是2^(n-1)
but，这里有个坑。比如说6=2*3，9=3*3，当6和9一起匹配的时候，3只会算一次，所以还应该去掉这些重复权重。
6有3，9也有3，那其实就是从没有3这个质因子的数字里去取出来匹配就好了
于是用一个num数组来记录每个质因子出现的次数，权重为2^(n-num[i]-1)
以下是基础代码:
num = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] ans = 0 A = [1,6,2] n = 3 for a in A: if a == 1: //1不用管了 continue canSplit = 0 //记录它能不能被分解，如果不能被分解，说明它自己就是质数 for i in range(2, a的根号): flag = 0 while a % i == 0: flag = 1 canSplit = 1 a = a /i if flag: ans = ans + (2**(n-1-num[i])) % (1e9+7) num[i] = num[i] + 1 if canSplit == 0: # 分解不了，他不是1，所以肯定本身就是质数 ans = ans + (2 ** (n - 1 - num[a])) % (1e9+7) num[a] = num[a] + 1 print(ans)
（1）由于没有写数字范围，质因子可以考虑先线性筛法筛出所有质数
（2）2^(num[i]-1)对1e9+7取模，应当使用快速幂
可以帮做题和答疑~私聊呗
飞鱼科技公司福利 177人发布