[CSP-S模拟测试]:gcd（莫比乌斯反演）

题目描述

有$n$个正整数$x_1\sim x_n$，初始时状态均为未选。有$m$个操作，每个操作给定一个编号$i$，将$x_i$的选取状态取反。每次操作后，你需要求出选取的数中有多少个互质的无序数对。

输入格式

第一行两个整数$n,m$。第二行$n$个整数$x_1\sim x_n$。接下来$m$行每行一个整数。

输出格式

$m$行，每行一个整数表示答案。

样例

样例输入：

4 5
1 2 3 4
1
2
3
4
1

样例输出：

0
1
3
5
2

数据范围与提示

对于$20\%$的数据，$n,m\leqslant 1,000$。
对于另外$30\%$的数据，$x_i\leqslant 100$。
对于$100\%$的数据，$n,m\leqslant 200,000$，$x_i\leqslant 500,000$，$1\leqslant i\leqslant n$。

题解

我们先来设三个量：

　　$\alpha.s(i)$表示为$i$的倍数的数的个数。

　　$\beta.g(i)$表示 $gcd$为$i$的倍数的数个数。

　　$\gamma.f(i)$表示$gcd$为$i$的数的个数。

$s(i)$很好就能求出，而$g(i)=\frac{s(i)\times (s(i)-1))}{2}$，但是我们需要的是$f(i)$，该怎么办呢？

显然，$g(i)=\sum \limits_{i|d}f(d)$，那有又什么用呢？

这里就需要用到一个神奇的东东了：第二类莫比乌斯反演（详见信息学奥赛之数学一本通P145中间）。

于是这个式子便变成了：$f(i)=\sum \limits_{i|d}\mu(\frac{d}{i})g(d)$。

现在我们需要考虑的就只有修改操作了，每次插入或删除一个数的时候只要暴力枚举其因数即可。

时间复杂度：$\Theta(m\sqrt{\max x_i})$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

int n,m;

long long a[200001];

long long s[500001],g[500001],f[500001];

long long mu[500001],prime[500001],cnt;

bool vis[200001],v[500001];

long long ans,mx;

void pre_work()

{

	mu[1]=1;

	for(int i=2;i<=mx;i++)

	{

		if(!v[i])mu[prime[cnt++]=i]=-1;

		for(int j=0;j<cnt&&i*prime[j]<=mx;j++)

		{

			v[i*prime[j]]=1;

			if(i%prime[j])mu[i*prime[j]]=-mu[i];

			else{mu[i*prime[j]]=0;break;}

		}

	}

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++)

		scanf("%lld",&a[i]),mx=max(mx,a[i]);

	pre_work();

	while(m--)

	{

		int x,flag;

		scanf("%d",&x);

		flag=a[x];

		if(vis[x])

		{

			for(int i=1;i*i<=flag;i++)

				if(!(flag%i))

				{

					s[i]--;

					ans-=mu[i]*g[i];

					g[i]=s[i]*(s[i]-1)/2;

					ans+=mu[i]*g[i];

					if(flag/i!=i)

					{

						s[flag/i]--;

						ans-=mu[flag/i]*g[flag/i];

						g[flag/i]=s[flag/i]*(s[flag/i]-1)/2;

						ans+=mu[flag/i]*g[flag/i];

					}

				}

			vis[x]=0;

		}

		else

		{

			for(int i=1;i*i<=flag;i++)

				if(!(flag%i))

				{

					s[i]++;

					ans-=mu[i]*g[i];

					g[i]=s[i]*(s[i]-1)/2;

					ans+=mu[i]*g[i];

					if(flag/i!=i)

					{

						s[flag/i]++;

						ans-=mu[flag/i]*g[flag/i];

						g[flag/i]=s[flag/i]*(s[flag/i]-1)/2;

						ans+=mu[flag/i]*g[flag/i];

					}

				}

			vis[x]=1;

		}

		printf("%lld\n",ans);

	}

	return 0;

}

rp++

巴特西