[Codeforces1097F][莫比乌斯反演]Alex and a TV Show

链接：https://codeforces.com/contest/1097/problem/F

看到GCD不难想到莫反
先考虑是次数怎么做
我们可以维护$f_i$表示$i$的倍数的有多少个
那么$1$操作可以根号维护
$2$操作可以直接加起来
$3$操作就是乘起来
$4$操作就是反演回去再做
考虑这里只用维护奇偶性，于是可以改为bitset
对应地，2操作就是$\text{xor}$，3操作就是$\text{and}$
1操作还是暴力根号
4操作反演回去的时候只需要考虑1的位，以及$mu$不为0的位
其中mu取1和-1是一样的，没有影响
因此，我们只需要知道，是1的位且这一位mu不为0的有多少个就可以了
对于每一个v再开一个bitset即可，最后$\text{and}$一下，看一下1的个数即可

CODE(peony_min)：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
using namespace std;
inline int read()
{
    int f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
    x=x*10+ch-'0';ch=getchar();}return x*f;
}
int stack[20];
inline void write(LL x)
{
    if(x<0){
    putchar('-');x=-x;}if(!x){
    putchar('0');return;}int top=0;while(x)stack[++top]=x%10,x/=10;while(top)putchar(stack[top--]+'0');
}
inline void pr1(int x){
    write(x);putchar(' ');}
inline void pr2(LL x){
    write(x);putchar('\n');}
const int MAXN=100005;
const int MAXM=7005;
bitset<MAXM> b1[MAXN],b2[MAXM],temp;
int n,Q;
int mu[MAXM],pr[MAXM],plen;bool vis[MAXM];
void getmu(int N)
{
    mu[1]=1;for(int i=2;i<=N;i++){
    if(!vis[i])pr[++plen]=i,mu[i]=-1;for(int j=1;j<=plen&&i*pr[j]<=N;j++){
    vis[i*pr[j]]=true;if(!(i%pr[j])){
    mu[i*pr[j]]=0;break;}mu[i*pr[j]]=-mu[i];}}
}
int main()
{
    getmu(MAXM-5);for(int i=1;i<=MAXM-5;i++)for(int j=1;j*i<=MAXM-5;j++)if(mu[j])	b2[i][i*j]=1;n=read();Q=read();while(Q--){
    int opt=read(),u1=read(),u2=read();if(opt==1){
    b1[u1].reset(); for(int i=1;i*i<=u2;i++)if(!(u2%i)){
    b1[u1][i]=b1[u1][i]^1;if(u2/i!=i)b1[u1][u2/i]=b1[u1][u2/i]^1;}}else if(opt==2){
    int u3=read();b1[u1]=b1[u2]^b1[u3];}else if(opt==3){
    int u3=read();b1[u1]=b1[u2]&b1[u3];}else{
    temp=b1[u1]&b2[u2];if(temp.count()&1)putchar('1');else putchar('0');}}return 0;
}