Description

维护 \(n\) 个初始为空的可重集，支持以下操作（操作总次数为 \(q\)）：

1 x v : 令集合 \(x\) 等于 \(\left\{v\right\}\)。

2 x y z : 令集合 \(x\) 等于集合 \(y\) 与 \(z\) 的并。

3 x y z : 令集合 \(x\) 等于集合 \(y\) 与 \(z\) 的积，\(A\times B=\left\{gcd(a,b)∣a∈A,b∈B\right\}\)。

4 x v : 询问 \(v\) 在集合 \(x\) 中出现次数模 \(2\) 的结果。

\(1\leq n\leq 10^5,1\leq q\leq 10^6,1\leq v\leq 7000\)。

Solution

对每个可重集 \(i\) 开一个 \(bitset\) : \(a[i]\)，\(a[i][j]\) 表示第 \(i\) 个集合中 \(j\) 的倍数出现次数模 \(2\)。

1 x v ：用 \(\mathcal O(\sqrt v)\) 的时间枚举 \(v\) 的约数 \(u\) 即可。

2 x y z ：\(a[x]=a[y]\ \text{xor}\ a[z]\)，\(\text{xor}\) 可以理解为模 \(2\) 意义下的加法。

3 x y z ：\(a[x]=a[y]\ \text{and}\ a[z]\)，\(\text{and}\) 可以理解为模 \(2\) 意义下的乘法。

4 x v ：设 \(f(n)\) 表示 \(n\) 在集合 \(x\) 中的出现次数，\(g(n)\) 表示 \(n\) 的倍数在集合 \(x\) 中的出现次数，那么有：$$g(n)=\sum_{n|d}f(d)?f(n)=\sum_{n|d}\mu(\frac{d}{n})g(d)$$

那么对每个数 \(n\) 开一个 \(bitset\) : \(miu[n]\)，其中 \(miu[n][d]=\mu(\lfloor\frac{d}{n}\rfloor)\% 2\)。

那么答案就是 \((a[x]\ \text{and}\ miu[v]).count()\) 模 \(2\)。

时间复杂度 \(\mathcal O(q(\sqrt v+\frac{v}{64}))\)。

#include 

using namespace std;

const int m = 7e3, e = 1e5 + 5, o = 7e3 + 5;
bitseta[e], b[o];
int miu[o], n, q;
bool bo[o];

template 
inline void read(t & res)
{
    char ch;
    while (ch = getchar(), !isdigit(ch));
    res = ch ^ 48;
    while (ch = getchar(), isdigit(ch))
    res = res * 10 + (ch ^ 48);
}

inline void init()
{
    int i, j;
    for (i = 1; i <= m; i++) miu[i] = 1;
    for (i = 2; i <= m; i++)
    if (!bo[i])
    {
        for (j = 2 * i; j <= m; j += i)
        {
            bo[j] = 1;
            if (j / i % i == 0) miu[j] = 0;
        }
    }
    for (i = 1; i <= m; i++)
    for (j = 1; i * j <= m; j++)
    b[i][i * j] = miu[j];
}

int main()
{
    int op, x, y, z, v, i;
    read(n); read(q);
    init();
    while (q--)
    {
        read(op);
        if (op == 1)
        {
            read(x); read(v); a[x].reset();
            int s = sqrt(v);
            for (i = 1; i <= s; i++)
            if (v % i == 0) a[x][i] = a[x][v / i] = 1;
        }
        else if (op == 2)
        {
            read(x); read(y); read(z);
            a[x] = a[y] ^ a[z];
        }
        else if (op == 3)
        {
            read(x); read(y); read(z);
            a[x] = a[y] & a[z];
        }
        else
        {
            read(x); read(v);
            putchar((((a[x] & b[v]).count()) & 1) + 48);
        }
    }
    return 0;
}