ZROI2018普转提day2t4-白红宇

ZROI2018普转提day2t4

阅读量：7194 次

发布时间：2019-06-29

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

分析

考场上暴力水过好评...

然后我的st表查询似乎是log的，然后log三方跑的比log方快，qwq。

我们发现如果一个区间的最小值就是这个区间的gcd，则这个区间合法。所以我们二分区间长度然后枚举起点检验是否合法即可。

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   using namespace std;const int LOG = 20;int n,a[500100],st1[500100][LOG+3],st2[500100][LOG+3],ans[500100],cnt;inline int gcd(int x,int y){ return y?gcd(y,x%y):x;}inline bool ck(int sum){ int i,j,k; if(sum==0)return 1; for(i=1;i+sum<=n;i++){ for(j=LOG;j>=0;j--) if((1<
                   
                    <=sum){ if(min(st1[i][j],st1[(i+sum)-(1<
                    
                     <
                     
                      =0;j--) if((1<
                      
                       <=sum){ if(min(st1[i][j],st1[(i+sum)-(1<
                       
                        <
                        
                         1){ int mid=(le+ri)>>1; if(ck(mid))le=mid; else ri=mid; } go(le); return 0;}