1994. 好子集的数目

注意到，而其中符合条件的整数只有个，显然可以考虑状压，直接枚举所有情况即可。

注意的处理，对于每一个状态，每个都是可取可不取，故有种情况。

枚举所有子集：初始为，那么为：。

代码：

class Solution {
public:
	int a[22]={2,3,5,6,7,10,11,13,14,15,17,19,21,22,23,26,29,30};
    int prime[11]={2,3,5,7,11,13,17,19,23,29};
    int ans,m,cnt[35];
    const int p=1e9+7;
	int numberOfGoodSubsets(vector<int>& nums) {
        m=nums.size();
		for(int i=0;i<m;i++){
			cnt[nums[i]]++;
		} 
		int zt=0;
		for(int i=0;i<18;i++){
			if(cnt[a[i]]){
				zt|=(1<<i);
			}
		}
		for(int i=zt;i>0;i=((i-1)&zt)){
			__int128 res=1;
			for(int j=0;j<18;j++){	
				if(i&(1<<j)){
					res*=(__int128)a[j];
				}
			}
			int ff=1;
			for(int j=0;j<10;j++){
				int c=0;
				while(res%(__int128)prime[j]==0){
					res/=(__int128)prime[j];
					c++;
				}
				if(c>1){
					ff=0;
					break;
				}
			}
			if(ff){
				long long res=1;
				for(int j=0;j<18;j++){	
					if(i&(1<<j)){
						res=res*(long long)cnt[a[j]]%p;
					}
				}
				ans+=res;
				if(ans>=p) ans-=p;
			}
		}
		for(int i=1;i<=cnt[1];i++){
			ans<<=1;
			if(ans>=p) ans-=p;
		} 
		return ans;
    }
};