Hello 2019 F 莫比乌斯反演 + bitset

https://codeforces.com/contest/1097/problem/F

题意

有n个多重集,q次询问,4种询问
1. 将第x个多重集置为v
2. 将第y和z多重集进行并操作,并赋值给x
3. 将第y和z多重集进行乘操作,并赋值给x,乘操作:将y的每一个元素和z的每个元素的gcd放进多重集中
4. 询问第x个多重集中有多少个v,并将个数%2输出

题解

• 因为个数%2,所以可以考虑用bitset
• 操作1需要将一个数的因数放进x中,这样两个数相与就能得出两个数的公因数,方便操作3处理
• 操作2对两个集合进行异或即可
• 操作3对两个集合进行与就能得出两个集合所有数相互的公因数
• 假如a,b的公因数是x的倍数,那么gcd(a,b)一定是x的倍数
• (g(n)=sum_{n|d}f(d) =>f(n)=sum_{n|d}mu(frac{d}{n})g(d)),操作4需要先预处理出(f(n)),将(f(n))放进一个多重集里,与x相与,然后x中1的个数就是答案

代码

#include<bits/stdc++.h>
#define M 7001
#define MAXN 100005
using namespace std;
bitset<M>miu[M];
bitset<M>a[MAXN];
int mu[M+5],pr[M],vi[M+5];
int n,q,x,v,y,z,kd,cnt;
void sieve(){
	mu[1]=1;
	for(int i=2;i<M;i++){
		if(!vi[i]){mu[i]=-1;pr[++cnt]=i;}
		for(int j=1;j<=cnt&&i*pr[j]<M;j++){
			vi[i*pr[j]]=1;
			if(i%pr[j]==0)break;
			mu[i*pr[j]]=-mu[i];
		}
	}
	for(int i=1;i<M;i++)
		for(int j=i;j<M;j+=i)
			if(mu[j/i])miu[i].set(j);
}
int main(){
	sieve();
	cin>>n>>q;
	while(q--){
		scanf("%d",&kd);
		if(kd==1){
			scanf("%d%d",&x,&v);
			a[x].reset();
			for(int i=1;i*i<=v;i++)
				if(v%i==0){
					a[x].set(i);a[x].set(v/i);
				}	
		}
		else if(kd==2){
			scanf("%d%d%d",&x,&y,&z);
			a[x]=a[y]^a[z];
		}else if(kd==3){
			scanf("%d%d%d",&x,&y,&z);
			a[x]=a[y]&a[z];
		}else{
			scanf("%d%d",&x,&v);
			bitset<M>tp=a[x]&miu[v];
			printf("%d",tp.count()%2);
		}
	}
}