[NOIP2019模拟赛]数数(gcd)

题目大意：

　　求l~r中有多少数与x互质，带单点修改

分析：

　　两个30的部分分很好打：

　　　　·n<=1000暴力O(nq)就好了

　　　　·$a_i<=100$用树状数组维护每个x的前缀和就好了

　　100分做法有两种，一种是莫比乌斯反演（我不会），还有一种就是bitset乱搞

　　我们先筛法筛出所有质数（大概不到10000个）然后对于每个质数建立一个bitset，表示对于第i个数在有第j个质数这个质因子

　　求有多少数与x互质转换为有多少数与x不互质就好了

　　对于每次询问把所有x的质因子找出来然后把这些数的bitset或起来再用类似前缀和的方法维护即可

　　时间复杂度$O(\frac{n*Q*logn}{32})$显然跑不满，所以卡一卡就过了（跑的比莫比乌斯反演快）

代码：（这里把两种部分分的打法也都写上了）

 #pragma GCC optimize("Ofast")

 #include<bits/stdc++.h>

 #define lowbit(x) (x&(-x))

 using namespace std;

 inline int read(){

     int ans=,f=;char chr=getchar();

     while(!isdigit(chr)){if(chr=='-')f=-;chr=getchar();}

     while(isdigit(chr)) {ans=(ans<<)+(ans<<)+chr-;chr=getchar();}

     return ans*f;

 }const int M = 5e4+;

 int n,m,a[M],Q,ans,gcd[][];

 struct P{

     int s[M];

     void Update(int x,int a){for(;x<=n;x+=lowbit(x)) s[x]+=a;}

     int Query(int x){int res=;for(;x;x-=lowbit(x)) res+=s[x];return res;}

 }t[];

 //-------------------------------------------------第一个30pts --------------------------------------------------

 inline void Solve_1(){//n*Q<=1000000

     while(Q--){

         int opt=read(),x;

         if(opt==)    x=read(),a[x]=read();

         else{

             int l=read(),r=read();

             x=read();ans=;

             for(int i=l;i<=r;i++)

                 if(__gcd(x,a[i])==)

                     ++ans;

             printf("%d\n",ans);

         }

     }

 }

 //---------------------------------------第二个30pts -----------------------------------------------------

 inline void Solve_2(){//Ai<=100

     for(int i=;i<=;++i)

         for(int j=;j<=;++j)

             gcd[i][j]=__gcd(i,j);

     for(int i=;i<=;i++)

         for(int j=;j<=n;j++)

             if(gcd[i][a[j]]==)

                 t[i].Update(j,);

     while(Q--){

         int opt=read();

         if(opt==){

             int x=read(),y=read(),tt=a[x];

             a[x]=y;

             for(int i();i<=;++i){

                 if(gcd[a[x]][i]!=&&gcd[tt][i]==)

                     t[i].Update(x,-);

                 if(gcd[a[x]][i]==&&gcd[tt][i]!=)

                     t[i].Update(x,);

             }

         }else{int l=read(),r=read(),x=read();

             printf("%d\n",t[x].Query(r)-t[x].Query(l-));

         }

     }

 }bitset<M>s[],now;

 int v[M*],pri[M*],tot;

 //----------------------------------------通解--------------------------------------------

 inline void Get_Pri(){

     for(int i=;i<=;i++){

         if(!v[i]) v[i]=i,pri[++tot]=i;

         for(int j=;j<=tot;j++){

             if(pri[j]>/i||pri[j]>v[i]) break;

             v[i*pri[j]]=pri[j];

         }

     }

 }

 inline void Update(int pos,int x,int y){

     int i=;

     while(){

         if(pri[i]*pri[i]>x) break;

         if(x%pri[i]==){

             s[i][pos]=y;

             while(x%pri[i]==) x/=pri[i];

         }i++;

     }if(x>)s[lower_bound(pri+,pri+tot+,x)-pri][pos]=y;

 }

 inline void Solve(){

     Get_Pri();

     for(int i=;i<=n;i++) Update(i,a[i],);

     while(Q--){

         int opt=read();

         if(opt==){

             int x=read(),y=read();

             Update(x,a[x],),Update(x,y,);

             a[x]=y;

         }else{

             int l=read(),r=read(),x=read();

             int i=;now=;

             while(){

                 if(pri[i]*pri[i]>x) break;

                 if(x%pri[i]==){

                     now|=s[i];

                     while(x%pri[i]==) x/=pri[i];

                 }i++;

             }if(x>) now|=s[lower_bound(pri+,pri+tot+,x)-pri];

             int Ans=r-l+-(now>>l).count()+(now>>(r+)).count();

             printf("%d\n",Ans);

         }

     }

 }

 int main(){

     freopen("gcd.in","r",stdin);

     freopen("gcd.out","w",stdout);

     n=read();

     for(int i=;i<=n;++i) a[i]=read();

     Q=read();

 //    if(n*Q<=1000000) Solve_1();

 //    else Solve_2();

     Solve();

     return ;

 }

巴特西

[NOIP2019模拟赛]数数(gcd)

最新文章

热门文章