CodeForces

分析

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

$1$ 操作预处理后直接赋值即可； $2$ 操作直接异或即可； $3$ 操作直接与即可。下面考虑 $4$ 操作怎么做。

设 $f(i)$ 表示 $i$ 作为因子的出现次数， $g(i)$ 表示 $i$ 的出现次数，那么有 $f(x)=\sum\limits_{x|d}g(d)$ ；莫比乌斯反演可得 $g(x)=\sum\limits_{x|d}\mu(\frac{d}{x})f(d)$ 。

维护一些 bitset ，假设叫 $Mu$ 。设 $\Mu_{i, j} (i|j)$ 表示 $\mu(\frac{j}{i})$ ，于是只要与一下，然后 $1$ 的个数就是答案了。

因为运算在模 $2$ 意义下进行，所以 $1$ 和 $-1$ 是一样的。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <bitset>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;
const int L=7000+10;

int v[L],p[L],cnt=0;
int mu[L];
bitset<L> bit[N],Mu[L],S[L];

inline void sieve(int n) {
    v[1]=mu[1]=1;
    for (re int i=2;i<=n;++i) {
        if (!v[i]) p[++cnt]=i,mu[i]=-1;
        for (re int j=1;j<=cnt&&i*p[j]<=n;++j) {
            v[i*p[j]]=1;
            if (i%p[j]) mu[i*p[j]]=-mu[i];
            else break;
        }
    }
    for (re int i=1;i<=n;++i)
        for (re int j=i;j<=n;j+=i)
            S[j][i]=1,Mu[i][j]=(mu[j/i]!=0);
}

int main() {
    sieve(7000);
    int n=read(),Q=read();
    while (Q--) {
        int op=read();
        if (op==1) {
            int x=read(),y=read();
            bit[x]=S[y];
        }
        else if (op==2) {
            int x=read(),y=read(),z=read();
            bit[x]=bit[y]^bit[z];
        }
        else if (op==3) {
            int x=read(),y=read(),z=read();
            bit[x]=bit[y]&bit[z];
        }
        else {
            int x=read(),y=read();
            printf("%d",(bit[x]&Mu[y]).count()&1);
        }
    }
    return 0;
}