\(Description\)
给定n个数(\(1\leq a_i\leq 5*10^5\))，每次从这n个数中选一个，如果当前集合中没有就加入集合，有就从集合中删去。每次操作后输出集合中互质的数对个数。
\(Solution1\)
考虑暴力一点，对于要修改的数分解质因数，集合中与它互质的数的个数就是 n-(有1个公共质因数)+(有2个公共质因数)-…
维护一下每种因子(可以是多个因数的积)对应集合中的多少个数就行。
真的好暴力。。但是一个数的质因子大多也就4.5个，so是没问题的。
（\(2*3*5*7*11*13*17>5*10^5\)，所以质因子的个数不会超过6个）
唉 一道水题写了一个多小时。。(写法有问题还一直T)
//171ms4700KB
#include <cstdio>
#include <cctype>
#include <algorithm>
//#define gc() getchar()
#define MAXIN 200000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
const int N=2e5+5,MAX=5e5+3;int n,Q,A[N],now,have[N],num[MAX],bit[23333],pcnt,P[N],cnt,p[233];
long long Ans;
bool not_P[MAX];
char IN[MAXIN],*SS=IN,*TT=IN;inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
void Pre(int n)
{
for(int i=2; i<=n; ++i)
{
if(!not_P[i]) P[++pcnt]=i;
for(int j=1; j<=pcnt && i*P[j]<=n; ++j)
{
not_P[i*P[j]]=1;
if(!(i%P[j])) break;
}
}
for(int i=1,s=0; i<=5000; ++i,s=0)
{
for(int j=0; j<=13; ++j)
if(i>>j & 1) ++s;
bit[i]=s;
}
}
void Div(int x)
{
cnt=0;
for(int i=1; i<=pcnt&&P[i]*P[i]<=x; ++i)//P[i]*P[i]<=x not P[i]<=x！不然就成O(n)的了！
if(!(x%P[i]))
{
p[cnt++]=P[i];
while(!(x%P[i])) x/=P[i];
}
if(x!=1) p[cnt++]=x;
}
void Add(int x,int val)
{
Div(A[x]);
long long ans=~val?now++:--now;//与除x以外的产生影响
for(int i=1; i<(1<<cnt); ++i)
{//枚举因子组合。。
int fac=1;
for(int j=0; j<cnt; ++j)
if(i>>j & 1) fac*=p[j];
if(val==-1) --num[fac];//不能算x本身！
if(bit[i]&1) ans-=num[fac]; else ans+=num[fac];
if(~val) num[fac]++;
}
Ans+=(long long)val*ans;
}int main()
{
n=read(), Q=read(); int mx=0;
for(int i=1; i<=n; ++i) mx=std::max(mx,A[i]=read()), have[i]=-1;
Pre(mx); int x;
while(Q--)
have[x=read()]*=-1, Add(x,have[x]), printf("%I64d\n",Ans);
return 0;
}
\(Solution2\)
gcd=1。。考虑反演。
令\(f(d)=\sum_{i=1}^n\sum_{j=1}^n[\gcd(a_i,a_j)=d]\)，\(F(d)=\sum_{i=1}^n\sum_{j=1}^n[d\mid\gcd(a_i,a_j)]\)，那么$$f(1)=\sum_{i=1}^n\mu(i)F(i)$$
令\(num[d]\)为含有\(d\)因子的数的个数，则\(F(d)=C_{num[d]}^2\)
这样每次操作只需要修改其因子的num即可。
//452ms6600KB(因为要枚举因数而不是只需要枚举质数 有点慢了)
#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
const int N=2e5+5,MAX=5e5+5;int n,cnt,A[N],P[N],mu[MAX],have[N],num[MAX];
long long Ans;
bool not_P[MAX];inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
void Pre(int n)
{
mu[1]=1;
for(int i=2; i<=n; ++i)
{
if(!not_P[i]) P[++cnt]=i, mu[i]=-1;
for(int j=1; j<=cnt&&i*P[j]<=n; ++j)
{
not_P[i*P[j]]=1;
if(i%P[j]) mu[i*P[j]]=-mu[i];
else {mu[i*P[j]]=0; break;}
}
}
}
void Add(int x,int val)
{
for(int i=1; i*i<=x; ++i)//包括1啊→_→
if(!(x%i))
{
Ans-=1ll*mu[i]*num[i]*(num[i]-1)>>1, num[i]+=val;
Ans+=1ll*mu[i]*num[i]*(num[i]-1)>>1;
if(i*i!=x)
{
int j=x/i;
Ans-=1ll*mu[j]*num[j]*(num[j]-1)>>1, num[j]+=val;
Ans+=1ll*mu[j]*num[j]*(num[j]-1)>>1;
}
}
}int main()
{
n=read(); int Q=read(),mx=0;
for(int i=1; i<=n; ++i) mx=std::max(mx,A[i]=read()), have[i]=-1;
Pre(mx); int x;
while(Q--)
have[x=read()]*=-1, Add(A[x],have[x]), printf("%I64d\n",Ans);
return 0;
}
