HDOJ5726解题报告【ST表】-白红宇

HDOJ5726解题报告【ST表】

阅读量：5239 次

发布时间：2019-06-14

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

题目地址：

　　http://acm.hdu.edu.cn/showproblem.php?pid=5726

题目概述：

　　给出n个数以及q个询问，每个询问有两个数l，r，求[l,r]区间的gcd以及区间gcd等于这个gcd的所有方案数。

大致思路：

　　乍一看线段树，但是这个题询问太多了，所以我们使用ST表来做这个题目。

　　区间max，min，gcd，lcm都可以用ST表来做，ST表在O(nlogn)的预处理之后，对每个询问的时间是O(1)的。

　　而对于方案数，根据gcd不增的性质，我们可以枚举左端点，二分右端点，预处理所有的gcd对应的方案数。

复杂度分析：

　　ST表的处理是O(nlogn)，方案数的预处理也是O(nlogn)，而对于每个询问复杂度是O(1)。总的时间复杂度为O(T*nlogn)。

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 using namespace std;#define sacnf scanf#define scnaf scanf#define maxn 100010#define maxm 18#define inf 1061109567#define Eps 0.000001const double PI=acos(-1.0);#define mod 1000000007#define MAXNUM 10000#define For(i,j,k) for(int (i)=(j);(i)<=(k);(i)++)#define mes(a,b) memset((a),(b),sizeof(a))typedef long long ll;typedef unsigned long long ulld;void Swap(int &a,int &b) { int t=a;a=b;b=t;}ll Abs(ll x) { return (x<0)?-x:x;}int st[maxn][maxm],n,mk;map
                 
                   q;int gcd(int a,int b){ if(a
                  
                   >1; if(query(l,m)==temp) l=m; else r=m-1; } q[temp]+=(l-j+1); j=l+1;temp=query(i,j); } }}int main(){ //freopen("data.in","r",stdin); //freopen("data.out","w",stdout); //clock_t st=clock(); int T;scanf("%d",&T); For(kase,1,T) { printf("Case #%d:\n",kase);mes(st,0); scanf("%d",&n); For(i,1,n) scanf("%d",&st[i][0]); for(int k=1;(1<
                   
                    <=n;k++) For(i,1,n-(1<