(codeforce547)C-Mike and Foam(质因子+容斥原理)

题目链接：Problem - 547C - Codeforces

题目：

样例输入： 

5 6
1 2 3 4 6
1
2
3
4
5
1

样例输出：

0
1
3
5
6
2

题意：一个酒吧，有n种啤酒，从1到n。第i瓶啤酒上面有ai毫升的泡沫。

有q个查询。每次查询给出一个编号，当编号为X的啤酒已经在货架上，那么就将其从货架上取下来，否则就应该把它放到货架上。每次询问后，应当输出架子的分数。货架的分数是满足i<j且gcd(ai,aj)=1的数对(i,j)的个数。

分析：这道题如果暴力求解的话复杂度就是O(n*q)，肯定是不能过的。比如现在已经有m种啤酒放在了货架上，此时货架的分数是x，那么我们再放入货架上一瓶啤酒，那么答案会比x多一个增量delt，我们就是要维护这种增量，这样放完啤酒后的分数就是x+delt了。同理，如果从货架上取下一瓶啤酒那么原理是一样的。

两瓶啤酒什么情况下才算是互质的呢？肯定是两者不含有公共的质因子，看一下数据范围发现a数组的范围是5e5,那么由于2*3*5*7*11*13*17=510510>5e5,所以每个数最多含有6个质因子，那么我们就可以对其质因子进行容斥定理，我们用一个num[s]记录质因子状态为s的数的个数，那么我们设A(p1,……,pk)表示含有质因子p1,……,pk，那么由于都是质数，我们可以用乘积来维护，也就是用num[s]记录质因子状态为s的数的个数。由于加入一个数和删除一个数基本上是类似的，下面我以加入一个数为例进行分析增量计算方法：

假如新加入的数为x，我们对x进行质因子分解得到p1,p2,……,pk，那么我们的增量就是,当计算完状态s的贡献后不要忘记将状态s的数量num[s]加一。

删除一个数与添加一个数唯一的不同就是，删除一个数是先将状态s的数量减1再计算该状态的贡献，而添加一个数是先算贡献再将状态s的数量加1。

由于a[]大小是小于5e5的，所以每个数的质因子最多有7个，那么对于每次询问容斥原理复杂度最多就是C(7,0)+C(7,1)+C(7,2)+C(7,3)+C(7,4)+C(7,5)+C(7,6)+C(7,7)=2^7,所以复杂度是肯定没问题的。

最后分享一个我在做题时遇到的一个低级bug，但是却很难发现错误所在，由于对于每个询问是给出的酒的编号t，所以可以直接用vis[t]标记酒是否在货架上，而我是直接用vis[a[t]]表示泡沫为a[t]的酒是否在货架上，由于可能会有两瓶编号不一样的酒的泡沫是一样的，所以就会出现问题。

下面是代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=1e6+10;
int num[N];//num[st]记录当前架子上的酒包含质因子状态为st的数的个数
bool vis[N];
long long a[N],p[N];
long long ans;
long long add(long long x)
{
	//预处理x的质因子 
	int tt=0;
	long long ans=0;
	for(int i=2;i*i<=x;i++)
	{
		if(x%i==0)
		{
			p[tt++]=i;
			while(x%i==0) x/=i;
		}
	}
	if(x!=1) p[tt++]=x;
	tt--;
	for(int s=0;s<1<<(tt+1);s++) 
	{
		long long f=1,t=1;
		for(int i=0;i<=tt;i++)
		{
			if(s>>i&1)
			{
				f*=-1;
				t*=p[i];
			}
		}
		if(t==1) t=0;//t==1说明没有更新，也就是状态为0 
		ans+=f*num[t];
		num[t]++;
	}
	return ans;
}
long long sub(long long x)
{
	//预处理x的质因子 
	int tt=0;
	long long ans=0;
	for(int i=2;i*i<=x;i++)
	{
		if(x%i==0)
		{
			p[tt++]=i;
			while(x%i==0) x/=i;
		}
	}
	if(x!=1) p[tt++]=x;
	tt--;
	for(int s=0;s<1<<(tt+1);s++) 
	{
		long long f=1,t=1;
		for(int i=0;i<=tt;i++)
		{
			if(s>>i&1)
			{
				f*=-1;
				t*=p[i];
			}
		}
		if(t==1) t=0;//t==1说明没有更新，也就是状态为0
		num[t]--;
		ans+=f*num[t];
	}
	return ans;
}
int main()
{
	int n,q; 
	cin>>n>>q;
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	while(q--)
	{
		long long t;
		scanf("%lld",&t);
		if(vis[t])
		{
			ans-=sub(a[t]);
			vis[t]=false;
		}
		else 
		{
			ans+=add(a[t]);
			vis[t]=true;
		}
		printf("%lld\n",ans);
	}
	return 0;
}