1994. The Number of Good Subsets¶
题目信息¶
- 题号:
1994
- 难度:
Hard
- 主题:
状态压缩、数论、动态规划
- 原题:
- 重点:
子集乘积必须是一个或多个不同质数的乘积,数组下标不同的选择分别计数
题目重述¶
统计非空子集数量,使其中元素乘积能够表示为若干不同质数的乘积,即没有质因数重复。结果取模。
自建示例¶
输入:nums = [1,2,3]
输出:6
解释:基础好子集 [2]、[3]、[2,3] 均可选择是否附加元素 1,共六种。
输入:nums = [4]
输出:0
解释:4 含重复质因数 2,不能构成好子集。