【题解】Alex and a TV Show 莫比乌斯反演+bitset ——quhengyi11

click here!

比赛的时候看这题过的人多也去看了看，结果发现自己压根不会处理操作 3，然后就弃了（太菜了 QAQ

首先因为 $v\leq 7000$并且询问的是一个数的奇偶性，我们容易想到将每个集合用一个大小为 $7000$的 $bitset$来维护每个数的奇偶性。

操作 $1,2,4$用这个思路都可以解决，但是关键是操作 $3$还是避免不了 $7000^2$复杂度的悲剧

题解给出了一种超级巧妙的设法，我们不要维护每个数出现了多少次，而是维护每个因子出现了多少次。

说一个栗子吧，当集合是酱紫的：$\{3,6\}$

那我们维护这个集合的时候就是酱紫的：$\{1,3,1,2,3,6\}$

因为只需要维护奇偶性所以实际上它是酱紫的：$\{2,6\}$

这样变化之后怎么进行操作呢？

操作 $1$：初始化每个数所对应的因数集合，给集合赋值这个数的时候就直接给维护的集合赋值这个因数集合就行

操作 $2$：取并集，因为我们维护的 $bitset$相当于是模 $2$意义下记录了每个因数的个数，取并集也就是将它们对应加起来，在模 $2$意义下显然就是异或操作

操作 $3$：取两集合的 $gcd$，考虑一个因数 $p$，它在集合 $A$中出现了 $a_p$次，在集合 $B$中出现了 $b_p$次，那么也就是说将 $A,B$集合取完 $gcd$后它一共出现了 $a_p\times b_p$次，在模 $2$意义下即逻辑乘 $and$一下就行了。

操作 $4$：询问一个数 $v$在集合中出现的次数的奇偶性。

哇你刚刚维护的都是因子数，问一个数的次数怎么办啊？

别急，我们设 $f(v)$表示数 $v$出现的次数

我们维护的实际上就是 $F(n)=\sum_{d|n}f(d)$个数的奇偶性

你知道 $F(n)$去求 $f(n)$不就是莫比乌斯反演的吗？

$$f(n)=\sum_{n|d}\mu(\frac d n)F(d)$$

$$f(n)=\sum_{T=1}^{\infty}\mu(T)F(Tn)$$

对于不同的 $n$，我们可以预处理一个 $\mu(T)$的，询问答案的时候将它们两个乘起来然后数 $1$的个数就行

具体来讲就是 $smu_{i,j}=(\mu(i\times j) \ne 0)$（因为维护奇偶性所以酱紫写就可以了

问集合 $x$里面有多少个 $v$，用集合 $s_x$和 $smu_v$取 $and$即可

代码

#include<bits/stdc++.h>
#define fo(i, a, b) for (ll i = (a); i <= (b); ++i)
#define fd(i, a, b) for (ll i = (a); i >= (b); --i)
#define mod 1000000007
#define ll long long
#define N 7005
#define M 100005
std::bitset<N> vis;
int mu[N], p[N], tot, n, q;
inline void init ()
{
    int n = N - 3;
    mu[1] = 1;
    fo (i, 2, n)
    {
        if (!vis[i])
            p[++tot] = i, mu[i] = -1;
        vis[i] = 1;
        for (int j = 1; j <= tot && i * p[j] <= n; ++j)
        {
            vis[i * p[j]] = 1;
            if (!(i % p[j])) break;
            mu[i * p[j]] = -mu[i];
        }
    }
}
std::bitset<N> s[M], e[N], smu[N]; 
int main ()
{
    init();
    scanf("%d %d", &n, &q);
    int up = 7000;
    fo (i, 1, up)
        for (int j = i, cnt = 1; j <= up; ++cnt, j += i)
            e[j][i] = 1, smu[i][j] = (mu[cnt] != 0);
    while (q--)
    {
        int opt, a, b, c;
        scanf("%d %d %d", &opt, &a, &b);
        if (opt == 1)
            s[a] = e[b];
        else
        if (opt == 2)
        {
            scanf("%d", &c);
            s[a] = s[b] ^ s[c];
        }
        else
        if (opt == 3)
        {
            scanf("%d", &c);
            s[a] = s[b] & s[c];
        }
        else
            printf("%d", (s[a] & smu[b]).count() & 1);
    }
    return 0;
}