gcd(NOIP 模拟测试 23)

题目大意:

有 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:

#include<iostream>
 #include<cstdio>
 #include<cmath>
 #define LL long long
 #define re register
 using namespace std;
 const int M=500010;
 const int N=200010;
 int n,m,cnt=0,ma;
 LL ans=0;
 int a[N],b[N],v[M],p[M];
 LL mu[M],g[M],s[M];
 inline int read()
 {
     re int s=0;char c=getchar();
     while(c<'0'||c>'9') c=getchar();
     while(c>='0'&&c<='9'){
         s=(s<<3)+(s<<1)+c-'0';
         c=getchar();
     }
     return s;
 }
 inline LL max(LL x,LL y)
 {
     return x>y?x:y;
 }
 void pre()
 {
     mu[1]=1;
     for(re int i=2;i<=ma;++i){
         if(v[i]==0){
             p[++cnt]=i;
             mu[i]=-1;
         }
         for(re int j=1;j<=cnt&&i*p[j]<=ma;++j){
             v[i*p[j]]=1;
             if(i%p[j]!=0) mu[i*p[j]]=-mu[i];
             else{
                 mu[i*p[j]]=0;
                 break;
             }
         }
     }
 }
 inline void add(re int x)
 {
     g[x]=g[x]+s[x];
     ans=ans+mu[x]*s[x];
     s[x]++;
 }
 inline void del(re int x)
 {
     g[x]=g[x]+1-s[x];
     ans=ans+mu[x]*(1-s[x]);
     s[x]--;
 }
 inline void work1(re int x)
 {
     for(re int i=1;i*i<=a[x];++i){
         if(a[x]%i==0){
             add(i);
             if(i*i!=a[x])
                 add(a[x]/i);
         }
     }
 }
 inline void work2(re int x)
 {
     for(re int i=1;i*i<=a[x];++i){
         if(a[x]%i==0){
             del(i);
             if(i*i!=a[x])
                 del(a[x]/i);
         }
     }
 }
 int main()
 {
     n=read();m=read();
     for(re int i=1;i<=n;++i){
         a[i]=read();
         ma=max(ma,a[i]);
     }
     pre();
     for(re int i=1;i<=m;++i){
         re int x=read();
         if(b[x]==0){
             b[x]=1;work1(x);
         }
         else{
             b[x]=0;work2(x);
         }
         printf("%lld\n",ans);
     }
     return 0;
 }
View Code

PS: 此题需要卡常.

来源: http://www.bubuko.com/infodetail-3158490.html