题目大意：
有N个数，初始时均不选，每次选择一个数将其选取状态取反，每次操作询问已选集合中互质数对个数。
直接求不好求，我们考虑容斥。
两个数互质的定义是最大公约数为一。
设$f[n]$为集合中gcd为n的数对个数，$g[n]$为集合中gcd为n的倍数的数对个数。
则有式子：
$g[n]= \sum _{n|d} f[d]$
这与莫比乌斯反演公式一致：
$F[n]= \sum _{n|d} f[d] \Longleftrightarrow f[n]=\sum _{n|d} \mu (\frac{d}{n}) F[d]$
经过反演得到：
$f[n]=\sum _{n|d} \mu (\frac{d}{n}) g[d]$
代入$n=1$
$f[1]=\sum _d \mu (d) g[d]$
设$s[n]$为集合中是n的倍数的数的个数。
显然：
$g[n]=C_{s[n]}^2=\frac{s[n]*(s[n]-1)}{2}$
先筛出莫比乌斯函数，然后就可以通过维护是$s[n]$来维护$g[n]$，再维护$f[1]$。
每次添加一个数时，枚举它的因数，$O(1)$修改$s[n]$，$g[n]$和$f[1]$。
时间复杂度$O(N*\sqrt{max(X_i)})$
Code：
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #define LL long long 5 #define re register 6 using namespace std; 7 const int M=500010; 8 const int N=200010; 9 int n,m,cnt=0,ma; 10 LL ans=0; 11 int a[N],b[N],v[M],p[M]; 12 LL mu[M],g[M],s[M]; 13 inline int read() 14 { 15 re int s=0;char c=getchar(); 16 while(c<‘0‘||c>‘9‘) c=getchar(); 17 while(c>=‘0‘&&c<=‘9‘){ 18 s=(s<<3)+(s<<1)+c-‘0‘; 19 c=getchar(); 20 } 21 return s; 22 } 23 inline LL max(LL x,LL y) 24 { 25 return x>y?x:y; 26 } 27 void pre() 28 { 29 mu[1]=1; 30 for(re int i=2;i<=ma;++i){ 31 if(v[i]==0){ 32 p[++cnt]=i; 33 mu[i]=-1; 34 } 35 for(re int j=1;j<=cnt&&i*p[j]<=ma;++j){ 36 v[i*p[j]]=1; 37 if(i%p[j]!=0) mu[i*p[j]]=-mu[i]; 38 else{ 39 mu[i*p[j]]=0; 40 break; 41 } 42 } 43 } 44 } 45 inline void add(re int x) 46 { 47 g[x]=g[x]+s[x]; 48 ans=ans+mu[x]*s[x]; 49 s[x]++; 50 } 51 inline void del(re int x) 52 { 53 g[x]=g[x]+1-s[x]; 54 ans=ans+mu[x]*(1-s[x]); 55 s[x]--; 56 } 57 inline void work1(re int x) 58 { 59 for(re int i=1;i*i<=a[x];++i){ 60 if(a[x]%i==0){ 61 add(i); 62 if(i*i!=a[x]) 63 add(a[x]/i); 64 } 65 } 66 } 67 inline void work2(re int x) 68 { 69 for(re int i=1;i*i<=a[x];++i){ 70 if(a[x]%i==0){ 71 del(i); 72 if(i*i!=a[x]) 73 del(a[x]/i); 74 } 75 } 76 } 77 int main() 78 { 79 n=read();m=read(); 80 for(re int i=1;i<=n;++i){ 81 a[i]=read(); 82 ma=max(ma,a[i]); 83 } 84 pre(); 85 for(re int i=1;i<=m;++i){ 86 re int x=read(); 87 if(b[x]==0){ 88 b[x]=1;work1(x); 89 } 90 else{ 91 b[x]=0;work2(x); 92 } 93 printf("%lld\n",ans); 94 } 95 return 0; 96 }
PS：此题需要卡常。
原文：https://www.cnblogs.com/hz-Rockstar/p/11366404.html
