hdu 5726 GCD

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

我把l写成了1，而且看了好久都没有看出来，实力眼瞎无限re。。。
就把所有的gcd求出来，然后存到一个set里面，线段树只是求gcd的，没别的ruan用

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=2e5+5;
ll gcd[maxn*4];
void pushup(int root)
{
    gcd[root]=__gcd(gcd[root<<1],gcd[root<<1|1]);
}
void update(int l,int r,int root,ll val,int pos)
{
    if(l==r)
    {
        gcd[root]=val;
        return ;
    }
    int mid=l+r>>1;
    if(mid>=pos)
        update(l,mid,root<<1,val,pos);
    else
        update(mid+1,r,root<<1|1,val,pos);
    pushup(root);
}
ll query(int l,int r,int root,int ql,int qr)
{
    if(l>=ql&&r<=qr)
        return gcd[root];
    ll ans=0;
    int mid=l+r>>1;
    if(mid>=ql)
        ans=query(l,mid,root<<1,ql,qr);
    if(mid<qr)
        ans=__gcd(ans,query(mid+1,r,root<<1|1,ql,qr));
    return ans;
}
map<ll,ll>ans,g,num;
map<ll,ll>::iterator it;
ll x[maxn];
int main()
{
    int t;
    scanf("%d",&t);
    int cas=0;
    while(t--)
    {
        int n,m,l,r;
        memset(gcd,0,sizeof(gcd));
        ans.clear(),g.clear(),num.clear();
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%lld",&x[i]),update(1,n,1,x[i],i);
        scanf("%d",&m);
        printf("Case #%d:n",++cas);
        for(int i=1;i<=n;i++)
        {
            num.clear();
            for(it=g.begin();it!=g.end();it++)
            {
                ll k=__gcd((ll)it->first,x[i]);
                num[k]+=it->second;
            }
            g.clear();
            for(it=num.begin();it!=num.end();it++)
                g[it->first]=it->second;
            for(it=g.begin();it!=g.end();it++)
                ans[it->first]+=it->second;
            ans[x[i]]++,g[x[i]]++;
        }
        while(m--)
        {
            scanf("%d%d",&l,&r);
            ll k=query(1,n,1,l,r);
            printf("%lld %lldn",k,ans[k]);
        }
    }
    return 0;
}

最后

以上就是任性花卷为你收集整理的hdu 5726 GCD的全部内容，希望文章能够帮你解决hdu 5726 GCD所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。