description
给定 n 个多重集，有 4 种操作：
（1）1 x v —— 将集合 x 变成单元素集合 {v}。
（2）2 x y z —— 将集合 x 变成集合 y 与集合 z 的并集。
（3）3 x y z —— 将集合 x 变成集合 y 与集合 z 的乘积。集合乘积 (A imes B) 定义为 ({gcd(a, b)|ain A, bin B})。
（4）4 x v —— 询问元素 v 在集合 x 中的出现次数 mod 2。
solution
先反演一波，求 (g(x, v)) 表示 (x) 中含有因子 (v) 的数量。则 (g(x,v)=sum_{v|d}f(x,d)mu(frac{d}{v}))。
对 2 取模时，相同元素可以消掉（即异或）。也就是说操作 2 是异或。
只有两个都含有因子 (v) 时，它们的 (gcd) 才会含有因子 (v)。也就是说操作 3 是取并。
那么开 n 个 bitset 维护一下即可。时间复杂度 (O(frac{qv}{w}))。
accepted code
#include <cmath>
#include <cstdio>
#include <bitset>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXV = 7000;
const int MAXN = 100000;
const int MAXQ = 1000000;
bitset<MAXV>a[MAXN + 5], b[MAXV + 5], c[MAXV + 5];
int mu[MAXV + 5];
bool check(int x) {int s = sqrt(x); return s * s == x;}
void init() {
for(int i=1;i<=MAXV;i++) mu[i] = 1;
for(int i=4;i<=MAXV;i++) {
if( !mu[i] || !check(i) ) continue;
mu[i] = 0;
for(int j=i;j<=MAXV;j+=i)
mu[j] = 0;
}
for(int i=1;i<=MAXV;i++)
for(int j=i;j<=MAXV;j+=i)
b[j - 1][i - 1] = 1, c[i - 1][j - 1] = mu[j / i];
}
int main() {
init(); int n, q;
scanf("%d%d", &n, &q);
for(int i=1,op,x,y,z,v;i<=q;i++) {
scanf("%d", &op);
if( op == 1 )
scanf("%d%d", &x, &v), v--, a[x] = b[v];
else if( op == 2 )
scanf("%d%d%d", &x, &y, &z), a[x] = a[y] ^ a[z];
else if( op == 3 )
scanf("%d%d%d", &x, &y, &z), a[x] = a[y] & a[z];
else {
scanf("%d%d", &x, &v), v--;
putchar(((a[x] & c[v]).count() & 1) + '0');
}
}
puts("");
}
details
其实写这篇博客的主要原因是解决一个困扰我多年的问题：怎么算空间开销。
计算机中空间的几个常见单位：
位（bit）：最小，只有 0/1；
字节（byte）：8bit；
千字节（KB）：1024byte；
兆字节（MB）：1024KB。
然后一般来说 c++ 变量都是以字节为单位存储，其中 bool/char 占 1 字节，int 占 4 字节，long long/double 占 8 字节。
不过 bitset 的存储是按位存储的，所以算空间开销的时候还要除以 8。因此不会 MLE（还绰绰有余）。