RGCDQ（线段树+数论）-白红宇

RGCDQ（线段树+数论）

阅读量：6220 次

发布时间：2019-06-21

本文共 1459 字，大约阅读时间需要 4 分钟。

题意：求n和m之间的全部数的素因子个数的最大gcd值。

分析：这题好恶心。看着就是一颗线段树。但本题有一定的规律，我也是后来才发现，我还没推出这个规律。就不说了，就用纯线段树解答吧。

由于个点数都小于1000000所以素因子个数不会超过7个所以建一个线段树，最以下一层是每一个节点的素因子个数为1，2。3，4，5，6。7的有多少个，父节点求和。终于查询的是n到m之间有多少个1，2，3。4。5，6，7然后存在就求一下gcd着最大就好了

本题最重要的时间和空间。显然线段数中的点不会非常大，所以採用short类型

代码例如以下：

#include 
     
      #include 
      #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   using namespace std;int gcd(int a,int b){ return (b==0)?a:gcd(b,a%b);}const int N=100000;int prime[N]={0};int num_prime=0;bool isNotPrime[N]={1,1};void su1(){ for(long i = 2 ; i < N ; i ++){ if(!isNotPrime[i]) prime[num_prime++]=i; for(long j = 0 ; j < num_prime &&i*prime[j]
                   
                    >1; if(id<=i)updat(id,j,l,i,2*mid); else updat(id,j,i+1,r,2*mid+1); a[mid][j]=a[2*mid][j]+a[2*mid+1][j];}int sum[8];void su(int l,int r,int mid,int ll,int rr){ if(l>=ll&&r<=rr){ for(int i=1;i<=7;i++) sum[i]+=a[mid][i]; return; } int i=(l+r)>>1; if(ll<=i)su(l,i,2*mid,ll,rr); if(rr>i)su(i+1,r,2*mid+1,ll,rr);}//建树，求和，这是重点int main(){ memset(a,0,sizeof(a)); su1();// for(int i=1;i<=100;i++){// if(isNotPrime[i])// cout<
                    <<" "<
                     
                      <
                      
                       >t; while(t--){ scanf("%d%d",&n,&m); memset(sum,0,sizeof(sum)); su(2,1000005,1,n,m); int ans=-1; for(int i=1;i<=7;i++) for(int j=1;j<=7;j++){ if(i==j){ if(sum[i]>1)ans=max(ans,gcd(i,j)); } else{ if(sum[i]>0&&sum[j]>0)ans=max(ans,gcd(i,j)); } }//这个地方就能够纯暴力了 printf("%d\n",ans); } return 0;}

转载地址：http://zpoja.baihongyu.com/

你可能感兴趣的文章