题目描述
有$n$个正整数$x_1sim x_n$，初始时状态均为未选。有$m$个操作，每个操作给定一个编号$i$，将$x_i$的选取状态取反。每次操作后，你需要求出选取的数中有多少个互质的无序数对。
输入格式
第一行两个整数$n,m$。第二行$n$个整数$x_1sim x_n$。接下来$m$行每行一个整数。
输出格式
$m$行，每行一个整数表示答案。
样例
样例输入：
4 5
1 2 3 4
1
2
3
4
1
样例输出：
0
1
3
5
2
数据范围与提示
对于$20\%$的数据，$n,mleqslant 1,000$。
对于另外$30\%$的数据，$x_ileqslant 100$。
对于$100\%$的数据，$n,mleqslant 200,000$，$x_ileqslant 500,000$，$1leqslant ileqslant n$。
题解
我们先来设三个量：
$alpha.s(i)$表示为$i$的倍数的数的个数。
$eta.g(i)$表示 $gcd$为$i$的倍数的数个数。
$gamma.f(i)$表示$gcd$为$i$的数的个数。
$s(i)$很好就能求出，而$g(i)=frac{s(i) imes (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(msqrt{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
",ans);
}
return 0;
}
rp++