hdu5726 GCD

╰半夏微凉° 2022-07-18 16:30 168阅读 0赞

# GCD #

**Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)**  
**Total Submission(s): 2487    Accepted Submission(s): 876**

Problem Description

Give you a sequence of    N(N≤100,000)  integers :    a1,...,an(0<ai≤1000,000,000). There are    Q(Q≤100,000)  queries. For each query    l,r  you have to calculate    gcd(al,,al\+1,...,ar)  and count the number of pairs  (l′,r′)(1≤l<r≤N)such that    gcd(al′,al′\+1,...,ar′)  equal    gcd(al,al\+1,...,ar).

Input

The first line of input contains a number    T, which stands for the number of test cases you need to solve.  
  
The first line of each case contains a number    N, denoting the number of integers.  
  
The second line contains    N  integers,    a1,...,an(0<ai≤1000,000,000).  
  
The third line contains a number    Q, denoting the number of queries.  
  
For the next    Q  lines, i-th line contains two number , stand for the    li,ri, stand for the i-th queries.

Output

For each case, you need to output “Case \#:t” at the beginning.(with quotes,    t  means the number of the test case, begin from 1).  
  
For each query, you need to output the two numbers in a line. The first number stands for    gcd(al,al\+1,...,ar)  and the second number stands for the number of pairs  (l′,r′)such that    gcd(al′,al′\+1,...,ar′)  equal    gcd(al,al\+1,...,ar).

Sample Input

1
    5
    1 2 4 6 7
    4
    1 5
    2 4
    3 4
    4 4

Sample Output

Case #1:
    1 8
    2 4
    2 4
    6 1

Author

HIT

Source

[2016 Multi-University Training Contest 1][]

题意：求区间的gcd的值，并且求与这个区间gcd相同的区间的个数。

分析：求区间的gcd值只要用线段树来维护就行了，当时比赛的时候竟然没想到。由于gcd最多只有log（1e9）个，因此可以暴力的枚举右端点统计不同的gcd的区间的个数。

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    #define F first
    #define S second
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;int f=1;
        while((c=getchar())<'0' || c>'9')if(c=='-')f=-1;
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res*f;
    }
    const int N=100010,MOD=1e9+7;
    map<int,ll> mp1,mp2,ans;
    map<int,ll>::iterator it;
    
    int b[N];
    struct st
    {
        int l,r,val;
    }a[N<<2];
    
    int gcd(int a,int b)
    {
        return b==0? a : gcd(b,a%b);
    }
    
    void build(int l,int r,int i)
    {
        a[i].l=l,a[i].r=r;  //这个都能漏掉。。。。
        if(l==r){
            a[i].val = b[l];
            return;
        }
        int mid = l+r>>1;
        build(l,mid,i<<1);
        build(mid+1,r,i<<1|1);
        a[i].val = gcd(a[i<<1].val,a[i<<1|1].val);
    }
    
    int query(int l,int r,int i)
    {
        if(a[i].l >= l && a[i].r <= r) return a[i].val;
        if(a[i].l > r || a[i].r < l) return 0;
        return gcd(query(l,r,i<<1),query(l,r,i<<1|1));
    }
    
    int main()
    {
        int T=in(),ca=1;
        while(T--)
        {
            mp1.clear();
            mp2.clear();
            ans.clear();
            int n=in();
            for(int i=1;i<=n;i++){
                b[i]=in();
            }
            mp1[b[1]]++;
            ans[b[1]]++;
            for(int i=2;i<=n;i++){
                mp2[b[i]]++;
                for(it=mp1.begin();it!=mp1.end();it++)
                {
                    int now = gcd(b[i],it->F);
                    mp2[now] += it->S;
                }
                mp1.clear();
                for(it=mp2.begin();it!=mp2.end();it++)
                {
                    mp1[it->F] = it->S;
                    ans[it->F] += it->S;
                }
                mp2.clear();
            }
            build(1,n,1);
            printf("Case #%d:\n",ca++);
            int m=in();
            for(int i=1;i<=m;i++){
                int l=in(),r=in();
                if(l > r) swap(l,r);
                int ret = query(l,r,1);
                printf("%d %I64d\n",ret,ans[ret]);
            }
        }
        return 0;
    }

[2016 Multi-University Training Contest 1]: http://acm.hdu.edu.cn/search.php?field=problem&key=2016+Multi-University+Training+Contest+1&source=1&searchmode=source