题意简述
给定 (n-1) 种物品，重要度分别为 ([2,n]) 。甲乙两者来拿若干件（可以为 (0)）物品。若甲拿的物品的重要度集合为 (S_1) ，乙拿的物品的重要度集合为(S_2) ，则一种合法的方案定义为 (forall xin S_1,forall yin S_2,gcd(x,y)=1) 。求拿物品的方案总数。
题目分析
既然两个集合的唯一限制是质因子无交集，那么不难往状压DP方面去思考。压 (500) 以内的全部质数？不是很可做的亚子，我们必须思考如何压缩状态。
状压DP非常重要的一点就是把本来看上去不可以压的东西通过一些小 trick 使得一些东西可以单独拿出来。比如在这个题目中，一个数不可能同时有两个大于 (19) 的质因数！
也就是说，当我们考虑某个质数 (p(p>19)) 时，我们只需注意所有小于等于 (19) 的质数及该质数满足条件，其他的质数可以暂时不作考虑。故我们只需要压 (19) 以内的质数——很幸运，只有 (8) 个。具体处理的时候，我们先将所有数按照最大的质数排序，大质数相同的一起处理。设两个数组f1[][]和f2[][]，分别表示当前质数只放在甲手里/只放在乙手里。于是就可以实现DP啦。
代码分享
for(int i=2;i<=n;++i){
if(!a[i].BIG||i==2||a[i].BIG!=a[i-1].BIG)
memcpy(f1,dp,sizeof dp),memcpy(f2,dp,sizeof dp);
for(int j=d;j>=0;--j)
for(int k=d;k>=0;--k){
if(j&k) continue;
if(!(a[i].s&k)) f1[j|a[i].s][k]=A(f1[j|a[i].s][k],f1[j][k]);
if(!(a[i].s&j)) f2[j][k|a[i].s]=A(f2[j][k|a[i].s],f2[j][k]);
}
if(!a[i].BIG||i==n||a[i].BIG!=a[i+1].BIG){
for(int j=d;j>=0;--j)
for(int k=d;k>=0;--k)
if(!(j&k))
dp[j][k]=A(f1[j][k],A(f2[j][k],p-dp[j][k]));
}
}