题目链接
题目解法
很牛的套路啊！
看到集合并，且只要求奇偶性的问题，第一个想到 \(bitset\)
\(1,2,4\) 操作都是好维护的，关键是第 \(3\) 个操作
看到 $\gcd $，首先想到莫反
令 \(c_{x,i}\) 为集合 \(x\) 中数 \(i\) 的出现次数
则 \(c_{x,i}=\sum\limits_{i|j}\sum\limits_{i|k}c_{y,j}c_{z,k}\times [(j,k)=i]\)
\(=\sum\limits_{j=1}\sum\limits_{k=1}c_{y,ij}c_{z,ik}\times \sum\limits_{d|j,d|k}\mu(d)\\
=\sum\limits_{d=1}\mu(d)\times (\sum\limits_{j=1}c_{y,idj})\times (\sum\limits_{k=1}c_{z,idk})\)
转化到这一步还是不好做
考虑不求 \(c_{x,i}\) 的奇偶性，而求 \(f(x,i)=\sum\limits_{i|d}c_{x,d}\) 的奇偶性
用一下莫反的基本公式，\(c_{x,i}=\sum\limits_{i|j}\mu(\frac{j}{i})f(x,j)\)
带入上面的式子可得 \(\sum\limits_{j=1}\mu(j)f(x,ij)=\sum\limits_{j=1}\mu(j)f(y,ij)f(z,ij)\)
不难推出，\(f(x,i)=f(y,i)f(z,i)\)，直接按位与即可
时间复杂度 \(O(\frac{qv}{\omega})\)
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
FF=0;int RR=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
FF*=RR;
}
const int V=7010,N=100010;
int n,m;bool mu[V];
bitset<V> trans[V],g[V],bs[N];
int main(){
read(n),read(m);
int B=7000;
F(i,1,B){
mu[i]=1;
F(j,2,i) if(i%(j*j)==0) mu[i]=0;
}
F(i,1,B) F(j,1,B/i) if(mu[j]) trans[i].set(i*j);
F(i,1,B) F(j,1,B/i) g[i*j].set(i);
while(m--){
int op,x,y,z;read(op),read(x),read(y);
if(op==1) bs[x].reset(),bs[x]=g[y];
else if(op==2) read(z),bs[x]=bs[y]^bs[z];
else if(op==3) read(z),bs[x]=bs[y]&bs[z];
else putchar(((bs[x]&trans[y]).count()&1)+48);
}puts("");
return 0;
}