Solution
一句话题意:求架子上和 \(x\) 互质的数的 个数=总个数-和 \(x\) 不互质的数的个数。
那么求和 \(x\) 不互质的数就是经典容斥问题了。
因为所有数都能以一个 \(\prod p_i^{k_i}\) 的形式表示出来,并且一个数的质因子个数最多有七个(因为 \(2\cdot 3\cdot 5\cdot 7\cdot 11 \cdot 13\cdot 17 >500000\) ),所以暴力枚举质数即可。
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10,A=5e5+10,P=6;
int n,p,a[N],prime[A],lnk[N][P+5],tot[A];
bool isprime[A],vis[N];
ll ans;
inline void init(int n){
isprime[0]=isprime[1]=true;prime[0]=0;
for(int i=2;i<=n;i++){
if(!isprime[i]) prime[++prime[0]]=i;
for(int j=1;j<=prime[0]&&i*prime[j]<=n;j++){
isprime[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
}
inline void query(int x,int op){
for(int i=0;i<(1<<lnk[x][0]);i++){
int now=1,cnt=0;
for(int j=1;j<=lnk[x][0];j++)
if(i&(1<<j-1)) now*=lnk[x][j],cnt++;
if(cnt&1) ans-=op*tot[now];
else ans+=op*tot[now];
}
}
inline void update(int x,int op){
for(int i=0;i<(1<<lnk[x][0]);i++){
int now=1;
for(int j=1;j<=lnk[x][0];j++)
if(i&(1<<j-1)) now*=lnk[x][j];
tot[now]+=op;
}
}
int main(){
scanf("%d%d",&n,&p);
init(500000);
for(int i=1,x;i<=n;i++){
scanf("%d",&x);
for(int j=1;j<=prime[0]&&prime[j]<=sqrt(x);j++)
if(x%prime[j]==0){
lnk[i][++lnk[i][0]]=prime[j];
while(x%prime[j]==0) x/=prime[j];
}
if(x>1) lnk[i][++lnk[i][0]]=x;
}
while(p--){
int x;
scanf("%d",&x);
if(!vis[x]) query(x,1),update(x,1);
else update(x,-1),query(x,-1);
vis[x]^=1;
printf("%lld\n",ans);
}
return 0;
}