1994. The Number of Good Subsets

题目信息

题号:

1994

难度:

Hard

主题:

状态压缩、数论、动态规划

原题:

LeetCode 1994

重点:

子集乘积必须是一个或多个不同质数的乘积,数组下标不同的选择分别计数

题目重述

统计非空子集数量,使其中元素乘积能够表示为若干不同质数的乘积,即没有质因数重复。结果取模。

自建示例

输入:nums = [1,2,3]
输出:6
解释:基础好子集 [2]、[3]、[2,3] 均可选择是否附加元素 1,共六种。
输入:nums = [4]
输出:0
解释:4 含重复质因数 2,不能构成好子集。