HDU 5726 GCD 求给定序列中与查询段相等的GCD个数-白红宇

HDU 5726 GCD 求给定序列中与查询段相等的GCD个数

阅读量：7103 次

发布时间：2019-06-28

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

一上来RMQ，以便于把查询等东西都弄成logn的。然后预处理，因为GCD有递减趋势，并且每次改变下降都减少至少一半，所以很快就会到1，剩下的直接加进去；如果很慢到1，那么中途相等的gcd就可以二分。此复杂度为2logn，暴力起始位置，每次向左移都是logn，所以复杂度是2nlogn。

下面上代码

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              using namespace std;map
               
                 mp;int n,T,ncas=0;int dp[200100][25];int fun(int pos,int val){ int l=1,r=pos; while (l
                
                 >1; int len=pos-mid+1; int now=-1; int x=pos; for (int k=20;k>=0;k--) { if (len&(1<
                 
                  >1;}int main(){ scanf ("%d",&T); while (T--) { mp.clear(); scanf ("%d",&n); for (int i=1;i<=n;i++) { scanf ("%d",&dp[i][0]); } for (int k=1;(1<
                  
                   <=n;k++)//RMQ记录当前点向左1<
                   
                    =1;i--) { int zuo=i-(1<
                    
                     =1;j--) { int temp=dp[j][0]; int you=j; if (all==-1) all=temp; else all=__gcd(all,temp); j=fun(i,all);//从这个位置向左找gcd相等的位置 int len=you-j+1;//这一段的gcd相等，都加进去 if (mp.find(all)==mp.end()) mp[all]=0;//一个gcd对应一堆个数 mp[all]+=1ll*len;//防爆 } } printf ("Case #%d:\n",++ncas); int Q; scanf ("%d",&Q); while (Q--) { int l,r; scanf ("%d%d",&l,&r);//查 int len=r-l+1; int x=r; int ans=-1; for (int k=20;k>=0;k--)//跳着gcd { if (len&(1<

转载于:https://www.cnblogs.com/nj-czy/p/5688014.html

你可能感兴趣的文章