根据题意，一个合法的集合不可能会有重复的元素（我们暂时将1移出nums不考虑），否则整体的乘积一定含有两个相同的质因数。另外约束中给出nums的数值不超过30，所以一个合法的集合的元素的个数不会超过30，并且彼此互异。同时我们考虑如果自身已经含有重复质因数的num，一定不能加入这个集合，比如2的倍数、3的倍数等等。所以集合的候选元素只可能有这些
{2,3,5,6,7,10,11,13,14,15,17,19,21,22,23,26,29,30}
总共是18个。合法的集合一定是这18个元素的一个组合，可能性就是2^18=2e6，穷举一下是可行的。
当然，并非这2^18中组合都是合法的。我们还需要检验每个组合里，是否有任意一对元素不满足互质的，所以需要套上一个18*18的检验。通过了校验之后，我们就可以计算这种组合有多少构造方法。假设这个组合由{a,b,c...}组成，那么能构成这种集合的数量就是count[a]*count[b]*count[c]*...
我们把所有组合所对应的集合数量都加起来，记做ret。此时再考虑元素1的影响：因为无论元素1是否加入集合、以及加入多少个，都不影响之前的那些集合的合法性。所以最终的答案就是 ret * 2^count[1].
上述的解法虽然用了bit mask，但本质不是状态压缩DP，仅仅是用了二进制数来方便枚举而已。并且时间复杂度刚刚过线。
我们有更巧妙的方法设计状态。我们不以nums的元素作为bit的含义，而是以30以内的质因数作为bit的含义。任何一个合法的集合，根据其所含元素的因式分解，必然对应着{2,3,5,7,11,13,17,19,23,29}的一个组合。其中的每个质因数在这个集合中只出现过一次。穷举所有的组合，只要2^10=1024种情况，效率高很多。
我们令dp[state]表示质因数组合为state所代表的集合有多少种构造方法。我们类似背包问题的思想，对于每个num，我们先分解质因数：如果它包含有重复的质因数就直接舍弃，因为它无法加入任何一个合法集合；否则的话根据它的质因数分解，我们可以得到类似的状态压缩编码encode。对于那些完全包含encode的state（即encode是state的子集），我们都可以更新那些dp[state] += dp[state-encode] * count[num]. 因为dp[state-encode]对应有多少种集合构造方法，在其基础上加上num，就构造出了dp[state]所对应的集合。
因为任何一个state所对应的质因数组合都是一个合法的集合，最终我们需要累加ret += sum{dp[state]}, state=1,2,...,(1<<10)
此外，请记得考虑元素1的影响：因为无论元素1是否加入集合、以及加入多少个，都不影响上述这些集合的合法性。所以最终的答案就是 ret * 2^count[1].