题解
这道题题解里说用莫比乌斯反演做（我这个蒟蒻怎么会做呢）
但是不会，所以我们另想方法，这里我们用容斥来做
我们先把500000以内的所有质数筛出来
每次读入编号的时候，先把编号对应的这个数分解质因数
然后我们dfs枚举这个数的质因子取或不取，我们用t来表示取的质因子个数，如果t为奇数，ans就加，反之就减（容斥原理）
#include<bits/stdc++.h>
#define N 200005
#define M 500005
#define ll long long
using namespace std;
int n,m,num,x,cnt,tot;
ll ans,s;
int a[N];
int prime[M],Count[M];
int t[];
bool flag[M],Flag[M];
void dfs(int now,int num,int mul,int p){
if (now>tot){
if (!p) Count[mul]--;
ans+=num*Count[mul];
if (p) Count[mul]++;
return;
}
dfs(now+,num,mul,p);
dfs(now+,-num,mul*t[now],p);
}
int main(){
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++)
scanf("%d",&a[i]);
int d=M-;
flag[]=true;
for (int i=;i<=d;i++){
if (!flag[i]) prime[++cnt]=i;
for (int j=;j<=cnt&&i*prime[j]<=d;j++){
flag[i*prime[j]]=true;
if (!(i%prime[j])) break;
}
}
ans=;
for (int i=;i<=m;i++){
scanf("%d",&x);
int k=a[x],num=;
tot=;
while (k>=prime[num]&&num<=cnt){
if (!flag[k]){
t[++tot]=k; k=;
break;
}
if (k%prime[num]==) t[++tot]=prime[num];
while (k%prime[num]==) k/=prime[num];
num++;
}
if (Flag[x]) dfs(,-,,);
else dfs(,,,);
Flag[x]^=;
printf("%lld\n",ans);
}
return ;
}