【CF1097F】Alex and a TV Show（bitset）
题面
题解
首先模\(2\)意义下用\(bitset\)很明显了。
那么问题在于怎么处理那个\(gcd\)操作。
然后就莫比乌斯反演一下：\(f[n]=\sum\limits_{n|d}g[d],g[n]=\sum\limits_{n|d}\mu(\frac{d}{n})f[d]\)，发现这样子搞完之后，如果要处理集合\(g\)的\(gcd\)操作，就是把\(g\)变成\(f\)之后再按位乘起来(二进制意义下的按位与)，再变回去就好了。
不难发现变成\(f\)后仍然可以处理加法操作(二进制下按位或)，所以就没有必要反复在\(f,g\)之间转换了，直接用\(f\)就好了。
最后计算答案的时候再变回去\(bitset.count()\)一下就知道答案了。
预处理\(\mu\)相关的\(bitset\)和每个单个数的\(f\)就可以所有操作都做到\(\frac{7000}{\omega}\)。
#include<iostream>
#include<cstdio>
#include<bitset>
using namespace std;
#define MAX 7001
bitset<MAX> S[100100],f[MAX],p[MAX];
int n,Q,mu[MAX];
int main()
{
scanf("%d%d",&n,&Q);mu[1]=1;
for(int i=1;i<MAX;++i)
for(int j=i+i;j<MAX;j+=i)mu[j]-=mu[i];
for(int i=1;i<MAX;++i)
for(int j=i;j<MAX;j+=i)f[j].set(i);
for(int i=1;i<MAX;++i)
for(int j=i;j<MAX;j+=i)if(mu[j/i])p[i].set(j);
while(Q--)
{
int opt,x,y,z;scanf("%d%d%d",&opt,&x,&y);
if(opt==1)S[x]=f[y];
else if(opt==2)scanf("%d",&z),S[x]=S[y]^S[z];
else if(opt==3)scanf("%d",&z),S[x]=S[y]&S[z];
else printf("%d",(S[x]&p[y]).count()&1);
continue;
}
return 0;
}