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

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

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

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

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

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

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

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

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

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

第四个操作

[Fleft( n ight) ext{表示}n ext{作为因子的出现次数，}fleft( n ight) ext{表示}n ext{的出现次数} \ Fleft( n ight) =sum_{n|d}{fleft( d ight)} \ fleft( n ight) =sum_{n|d}{mu left( lfloor frac{d}{n} floor ight) Fleft( d ight)} ]

很刻意地为了让 and能得到答案，把 (mu left( lfloor frac{d}{n} floor ight) ext{和}Fleft( d ight)) 对应起来，每个数开一个bitset Mu，Mu[n][d]存 (mu left( lfloor frac{d}{n} floor ight))

然后&以后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, op, x, 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;
}