hdu 5726(二分)-白红宇

hdu 5726(二分)

阅读量：7222 次

发布时间：2019-06-29

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

GCDTime Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 1233    Accepted Submission(s): 382Problem DescriptionGive you a sequence of N(N≤100,000) integers : a1,...,an(0

/*难点在于计数，关键要发现gcd的递减性对于1到n的(l,r)对于固定的lgcd(l,r)>=gcd(l,r+1)对于固定的rgcd(l,r)<=gcd(l+1,r)因此可以不用逐一地进行计数方法为：枚举每一个左区间,对满足gcd(l,ri)的右区间进行二分查找跳跃着进行计数*/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           #define scan1(x) scanf("%d",&x)#define scan2(x,y) scanf("%d%d",&x,&y)#define scan3(x,y,z) scanf("%d%d%d",&x,&y,&z)using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int Max=1e6+10;int dp[Max][30];map
           
             vis;int A[Max];int gcd(int x,int y){ if(x
            
             >1; d2=RMQ(i,mid); if(d2>=d1) l=mid+1,ans=mid; else r=mid-1; } if(vis.find(d1)!=vis.end()) vis[d1]+=(ans-nex)+1; nex=r+1; } } printf("Case #%d:\n",ca++); for(int i=1; i<=m; i++) { ans=RMQ(L[i],R[i]); printf("%d %lld\n",ans,vis[ans]); } } return 0;}