hdu5726 GCD（倍增+二分or线段树+预处理）

女爷i 2021-11-10 23:52 264阅读 0赞

## 题意：给你n个数a1,a2,a3...an(n<=1e5,1<=ai<=1e9)，给你q个询问\[l,r\]。问你gcd(al,al+1,al+2...ar)为多少？再问你有多少个pair(l',r')(1<=l'<=r'<=n)使得gcd(al',al'+1...ar')与gcd(al,al+1,al+2...ar)为多少？   分析： ##

## 方法一：倍增+二分。先rmq预处理gcd，我们枚举左端点，然后一直往n方向一直gcd下来，我们发现gcd一直是减小的，而且我们发现他最多下降30次(2^30为1e9左右)。 ##

## 可以通过二分去求，再统计起来。 ##

## 方法二：线段树+预处理。map存储gcd的个数和种类，以a\[i\]为右端点进行扫描，右端点不断向后移动，以a\[i\]为右端点的gcd=gcd(以a\[i-1\]为右端点的gcd，a\[i\])，我们通过记录以前一个元素为右端点的gcd，然后扫描就可以了，因为最多会有logn个，这样就可以求出所有子区间的gcd种类和个数。 ##

## 代码一（方法一）： ##

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int N = 1e5+5;
    int t,n,q,a[N],f[N][20];
    
    void st() {
        for(int i=1;i<=n;i++) f[i][0]=a[i];
        int t = log(n) / log(2) + 1;
        for(int j = 1; j < t; j++)
            for(int i = 1; i <= n - (1<<j) + 1; i++)
                f[i][j] = __gcd(f[i][j-1], f[i + (1<<(j-1))][j-1]);
    }
    
    int qu(int l,int r) {
        int k = log(r - l + 1) / log(2);
        return __gcd(f[l][k], f[r - (1<<k) + 1][k]);
    }
    
    map<int,ll> ma;
    void init() {
        ma.clear();
        st();
        for(int i = 1; i <= n; i++) {
            int l = i,r = n,gd = a[i],ans,mid,st;
            while(1) {
                st = l;
                while(l <= r) {
                    mid = (l + r) >> 1;
                    if(qu(i,mid) < gd) r = mid - 1;
                    else ans = mid, l = mid + 1;
                }
                ma[gd] += ans - st + 1;
                gd = qu(i,l);
                r = n;
                if(l > r) break;
            }
        }
    }
    
    int main(){
        scanf("%d",&t);
        for(int cas = 1; cas <= t; cas++) {
            printf("Case #%d:\n",cas);
            scanf("%d",&n);
            for(int i=1;i<=n;i++) scanf("%d",&a[i]);
            init();
            scanf("%d",&q);
            while(q--) {
                int ql,qr;
                scanf("%d%d",&ql,&qr);
                printf("%d %lld\n",qu(ql,qr),ma[qu(ql,qr)]);
            }
        }
    	return 0;
    }

## 代码二（方法二）： ##

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int N = 1e5+5;
    int t,n,q,a[N],gd[4*N];
    map<int,ll> mp1,mp2,cnt;
    
    void bd(int o,int l,int r) {
        if(l == r) {
            gd[o]=a[l];
            return ;
        }
        int m = (l + r) >> 1;
        bd(2*o,l,m);
        bd(2*o+1,m+1,r);
        gd[o]=__gcd(gd[2*o],gd[2*o+1]);
    }
    
    int qu(int o,int l,int r,int ql,int qr) {
        if(ql <= l && qr >= r) return gd[o];
        int m = (l + r) >> 1;
        if(qr <= m) return qu(2*o,l,m,ql,qr);
        else if(ql > m) return qu(2*o+1,m+1,r,ql,qr);
        else return __gcd(qu(2*o,l,m,ql,qr),qu(2*o+1,m+1,r,ql,qr));
    }
    
    void init() {
        bd(1,1,n);
        mp1.clear(),mp2.clear(),cnt.clear();
        for(int i = 1; i <= n; i++) {
            cnt[a[i]]++;
            mp2[a[i]]++;
            for(auto it:mp1)
            {
                ll k=__gcd(a[i],it.first);
                cnt[k]+=it.second;
                mp2[k]+=it.second;
            }
            mp1.clear();
            for(auto it:mp2)
                mp1[it.first]=it.second;
            mp2.clear();
        }
    }
    
    int main(){
        scanf("%d",&t);
        for(int cas = 1; cas <= t; cas++) {
            printf("Case #%d:\n",cas);
            scanf("%d",&n);
            for(int i=1;i<=n;i++) scanf("%d",&a[i]);
            init();
            scanf("%d",&q);
            while(q--) {
                int ql,qr;
                scanf("%d%d",&ql,&qr);
                printf("%d %lld\n",qu(1,1,n,ql,qr),cnt[qu(1,1,n,ql,qr)]);
            }
        }
    	return 0;
    }