CF1097F Alex and a TV Show

考虑用 bitset 维护答案，显然操作 $3$ 难以维护，因为需要约数信息。考虑维护约数集合，考虑如何得到答案。
$$
\begin {aligned}
& \sum _ {i \in S} [i = x] \\
= & \sum _ {i \in S} [\frac i x = 1] \\
= & \sum _ {i \in S} \sum _ {d | \frac i x }\mu(d) \\
= & \sum _ {d \in S ‘, x | d} \mu(\frac d x) \\
\end {aligned}
$$
预处理出 $\mu$ ，范围内一个数的所有约数、倍数，用 bitset 维护即可。

查看代码

#include <cstdio>
#include <bitset>
using namespace std;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
const int N = 1e5 + 10, K = 7e3 + 10 + 10;
int n, m;
bitset<K> p[K], q[K], w[N], mu;
int main()
{
    read(n), read(m);
    mu.set();
    for (int i = 2; i * i < K; i++)
        for (int j = 1; i * i * j < K; j++)
            mu[i * i * j] = 0;
    for (int i = 1; i < K; i++)
        for (int j = 1; i * j < K; j++)
            p[i * j][i] = 1, q[i][i * j] = mu[j];
    for (int op; m; m--)
    {
        read(op);
        if (op == 1)
        {
            int x, y;
            read(x), read(y);
            w[x] = p[y];
        }
        else if (op == 2)
        {
            int x, y, z;
            read(x), read(y), read(z);
            w[x] = w[y] ^ w[z];
        }
        else if (op == 3)
        {
            int x, y, z;
            read(x), read(y), read(z);
            w[x] = w[y] & w[z];
        }
        else if (op == 4)
        {
            int x, y;
            read(x), read(y);
            write((w[x] & q[y]).count() & 1);
        }
    }
    return 0;
}