Codeforces Hello 2019 F. Alex and a TV Show[bitset+莫比乌斯

题意：维护n个集合，支持4种操作

1.将第x个集合赋值成{y}

2.将第x个集合赋值成 第y个集合和第z个集合的并

3.将第x个集合赋值成 (left{ text{gcd}left( a,b right) mid ain Y,bin Z right})

4.查询v在第x个集合里出现次数的奇偶性

注意n的范围是7000，值域也是7000 而不是1e5

看到这个范围和第四个操作（只需要奇偶性）很容易想到bitset，但开始想用bitset维护值域，想了一年还是不会快速做第三个操作。。。

对于每个集合维护一个bitset，第i位表示i作为因数在这个集合里出现次数的奇偶性

这样第一个操作直接处理完以后赋值，第二个操作就是取一个xor，第三个操作就是取and（有点难想，但我似乎说不太清）

第四个操作

[ Fleft( n right) text{表示}ntext{作为因子的出现次数，}fleft( n right) text{表示}ntext{的出现次数} Fleft( n right) =sum_{n|d}{fleft( d right)} fleft( n right) =sum_{n|d}{mu left( lfloor frac{d}{n} rfloor right) Fleft( d right)} ]
很刻意地为了让 and能得到答案，把 (mu left( lfloor frac{d}{n} rfloor right) text{和}Fleft( d right)) 对应起来，每个数开一个bitset Mu，Mu[n][d]存 (mu left( lfloor frac{d}{n} rfloor right))

然后&以后1的个数就是答案了

bitset<7003>a[MAXN],G[7003],Mu[7003];
int mu[7003],prime[7003],notprime[7003],cnt;
inline void Get() {
  mu[1] = notprime[1] = 1;
  lop(i,2,7000) {
    if (!notprime[i]) prime[++cnt] = i,mu[i] = -1;
    for (int j = 1; j <= cnt && i * prime[j] <= 7000; ++j) {
      notprime[i * prime[j]] = 1;
      if (i % prime[j] == 0) break;
      mu[i * prime[j]] = -mu[i];
    }
  }
}
int n,Q,op,x,y,z;
int main() {
  Get();
  for (int i = 1; i <= 7000; i++)
    for (int j = i; j <= 7000; j += i)
      G[j][i] = 1,Mu[i][j] = mu[j / i] != 0; //对于 对奇偶性的影响而言1和-1一样
  in,n,Q;
  while (Q--) {
    in,y;
    if (op == 1) a[x] = G[y];
    else if (op == 2) {
      in,z;
      a[x] = a[y] ^ a[z];
    }
    else if (op == 3) {
      in,z;
      a[x] = a[y] & a[z];
    }
    else putchar(((a[x] & Mu[y]).count() & 1) + '0'); 
  }
  return 0;
}