题目链接

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1439
参考博客：https://www.cnblogs.com/hua-dong/p/9141249.html

题意：

给 $N$N 个数，然后 $Q$Q 次询问，每次询问一个 $id$id ，如果这个 $id$id 没有出现过，就在集合中添加一个 $a\left[id\right]$a[id] ，如果出现过就把 $a\left[id\right]$a[id] 删去，换句话说，就是每个下标只能选或者不选，但是里面的数重复不重复无所谓，然后每次操作完询问集合里面互质的对数有多少种

思路：

我看的这个博客是计算每次加进去或取出来的这个数，与当前集合互质的对数
但是怎么求喃？这个是个关键：
根据博客的意思：add= $\mu \left(1\right)\cdot$μ(1)⋅含有因子1的个数+ $\mu \left(2\right)\cdot$μ(2)⋅含有因子2的个数+ $\mu \left(3\right)\cdot$μ(3)⋅含有因子3的个数+ $\mu \left(4\right)\cdot$μ(4)⋅含有因子4的个数+…+…
也就是说假如这个数 $x$x 含有因子 $d_1,d_2,d_3,d_4$d1​,d2​,d3​,d4​…
add=+ $\mu \left(d_1\right)\cdot$μ(d1​)⋅含有因子 $d_1$d1​ 的个数+ $\mu \left(d_2\right)\cdot$μ(d2​)⋅含有因子 $d_2$d2​ 的个数+ $\mu \left(d_3\right)\cdot$μ(d3​)⋅含有因子 $d_3$d3​ 的个数+ $\mu \left(d_4\right)\cdot$μ(d4​)⋅含有因子 $d_4$d4​ 的个数

然后我还学到了一个筛出每个数所有的因子的方法，嘿嘿嘿~

#include"bits/stdc++.h"
using namespace std;
typedef long long LL;
const int maxn=5e5+5;
const int MOD=1e9+7;
int Fac[maxn],a[maxn];//Fac[i]表示i这个因子有多少个 
vector<int>prime,factor[maxn];
bool vis[maxn];
int mu[maxn];
void PHI(int n)
{
	memset(vis,1,sizeof(vis));
	mu[1]=1;
	for(LL i=1;i<=n;i++)
	{
		for(LL j=1;i*j<=n;j++)//筛因子 
		{
			factor[i*j].push_back(j);
		}
		if(i==1)continue;//筛质数要从2开始 
		if(vis[i])
		{
			prime.push_back(i);
			mu[i]=-1;
		}
		for(LL j=0;j<prime.size()&&i*prime[j]<=n;j++)
		{
			vis[i*prime[j]]=0;
			if(i%prime[j]==0)
			{
				mu[i*prime[j]]=0;
				break;
			}
			else mu[i*prime[j]]=-mu[i];
		}
	}
}
bool has[maxn];//来看下标为i的出现过没得 
int main()
{
	PHI(maxn-5);
	int N,M;
	while(cin>>N>>M)
	{
		memset(Fac,0,sizeof Fac);
		memset(has,0,sizeof has);
		LL ans=0;
		for(int i=1;i<=N;i++)scanf("%d",a+i);
		while(M--)
		{
			int id,t;
			scanf("%d",&id);
			t=a[id];
			int d;
			if(has[id])
			{
				for(int j=0;j<factor[t].size();j++)d=factor[t][j],Fac[d]--;
				for(int j=0;j<factor[t].size();j++)d=factor[t][j],ans-=mu[d]*Fac[d];
			}
			else
			{
				for(int j=0;j<factor[t].size();j++)d=factor[t][j],ans+=mu[d]*Fac[d];
				for(int j=0;j<factor[t].size();j++)d=factor[t][j],Fac[d]++;
			}
			has[id]^=1;
			cout<<ans<<endl;
		}
		
	}
}