题解 

这道题题解里说用莫比乌斯反演做（我这个蒟蒻怎么会做呢）

但是不会，所以我们另想方法，这里我们用容斥来做

我们先把500000以内的所有质数筛出来

每次读入编号的时候，先把编号对应的这个数分解质因数

然后我们dfs枚举这个数的质因子取或不取，我们用t来表示取的质因子个数，如果t为奇数，ans就加，反之就减（）

1 #include
      
        2 #define N 200005 3 #define M 500005 4 #define ll long long 5 using namespace std; 6 int n,m,num,x,cnt,tot; 7 ll ans,s; 8 int a[N]; 9 int prime[M],Count[M];10 int t[100];11 bool flag[M],Flag[M];12 void dfs(int now,int num,int mul,int p){13     if (now>tot){14         if (!p) Count[mul]--;15         ans+=num*Count[mul];16         if (p) Count[mul]++; 17         return;18     }19     dfs(now+1,num,mul,p);20     dfs(now+1,-num,mul*t[now],p);21 }22 int main(){23     scanf("%d%d",&n,&m);24     for (int i=1;i<=n;i++)25         scanf("%d",&a[i]);26     int d=M-5;27     flag[1]=true;28     for (int i=2;i<=d;i++){29         if (!flag[i]) prime[++cnt]=i;30         for (int j=1;j<=cnt&&i*prime[j]<=d;j++){31             flag[i*prime[j]]=true;32             if (!(i%prime[j])) break;33         }34     }35     ans=0;36     for (int i=1;i<=m;i++){37         scanf("%d",&x);38         int k=a[x],num=1;39         tot=0;40         while (k>=prime[num]&&num<=cnt){41             if (!flag[k]){42                 t[++tot]=k; k=1;43                 break;44             }45             if (k%prime[num]==0) t[++tot]=prime[num];46             while (k%prime[num]==0) k/=prime[num];47             num++;48         }49         if (Flag[x]) dfs(1,-1,1,0); 50                 else dfs(1,1,1,1);51         Flag[x]^=1;52         printf("%lld\n",ans);53     } 54     return 0;55 }