GCD

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2530 Accepted Submission(s): 895

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

题意：给你n个数字组成的序列（n<=1e5），接下来q（<=1e5）个询问，每个询问包括一个区间[l,r]。求该区间内数字的GCD，以及整个[1,n]区间上有多少个子区间GCD等于该区间GCD；

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <map>

#include <vector>

#include <queue>

#include <cstring>

#include <string>

#include <algorithm>

using namespace std;

typedef  long long  ll;

typedef unsigned long long ull;

#define MM(a,b) memset(a,b,sizeof(a));

#define inf 0x7f7f7f7f

#define FOR(i,n) for(int i=1;i<=n;i++)

#define CT continue;

#define PF printf

#define SC scanf

const int mod=1000000007;

const int N=3*1e5+10;

int n,a[N],l[N],r[N];

struct node{

   int l,r;

   ll sum,lazy;

   int gcdn;

   void fun(ll v){

       this->lazy+=v;

       sum+=v*(r-l+1);

   }

   int mid(){

       return (l+r)>>1;

   }

}tree[4*N],tree2[4*N];

int gcd(int a,int b)

{

    if(b==0) return a;

    else return gcd(b,a%b);

}

void build(int k,int l,int r)

{

   tree[k].l=l;tree[k].r=r;

   if(l==r)

    {

        tree[k].gcdn=a[l];

        return;

    }

   int mid=(l+r)>>1;

   build(2*k,l,mid);

   build(2*k+1,mid+1,r);

   tree[k].gcdn=gcd(tree[2*k].gcdn,tree[2*k+1].gcdn);

}

ll query(int k,int l,int r)

{

    if(l<=tree[k].l&&tree[k].r<=r) return tree[k].gcdn;

    else {

        int mid=tree[k].mid();

        int gcdk=0;

        if(l<=mid) gcdk=query(2*k,l,r);

        if(r>mid)  gcdk=gcdk==0?query(2*k+1,l,r):gcd(gcdk,query(2*k+1,l,r));

        return gcdk;

    }

}

map<int,ll> tmp,tmpnext,ans;

map<int,ll>::iterator it;

void init()

{

    tmp.clear();ans.clear();

    for(int i=1;i<=n;i++)

    {

        tmpnext.clear();

        tmpnext[a[i]]++;

        for(it=tmp.begin();it!=tmp.end();++it)

        {

            int k=gcd(a[i],it->first);

            tmpnext[k]+=it->second;

        }

        for(it=tmpnext.begin();it!=tmpnext.end();it++)

                ans[it->first]+=it->second;

        tmp=tmpnext;

    }

}

int main()

{

    int cas,q,kk=0;

    scanf("%d",&cas);

    while(cas--)

    {

        scanf("%d",&n);

        for(int i=1;i<=n;i++) scanf("%d",&a[i]);

        build(1,1,n);

        init();

        scanf("%d",&q);

        for(int i=1;i<=q;i++)   scanf("%d%d",&l[i],&r[i]);

        printf("Case #%d:\n",++kk);

        for(int i=1;i<=q;i++)

        {

            int k=query(1,l[i],r[i]);

            printf("%d %lld\n",k,ans[k]);

        }

    }

    return 0;

}

题解链接：　　

我们注意观察gcd(a_{l},a_{l+1},...,a_{r})gcd(al,al+1,...,ar)，当l固定不动的时候，r=l...nr=l...n时，我们可以容易的发现,随着rr的増大，gcd(a_{l},a_{l+1},...,a_{r})gcd(al,al+1,...,ar)是递减的，同时gcd(a_{l},a_{l+1},...,a_{r})gcd(al,al+1,...,ar)最多有log\ 1000,000,000log 1000,000,000个不同的值，为什么呢？因为a_{l}al最多也就有log\ 1000,000,000log 1000,000,000个质因数

所以我们可以在log级别的时间处理出所有的以L开头的左区间的gcd(a_{l},a_{l+1},...,a_{r})gcd(al,al+1,...,ar)

那么我们就可以在n\ log\ 1000,000,000n log 1000,000,000的时间内预处理出所有的gcd(a_{l},a_{l+1},...,a_{r})gcd(al,al+1,...,ar)

然后我们可以用一个map来记录，gcd值为key的有多少个然后我们就可以对于每个询问只需要查询

对应gcd(a_{l},a_{l+1},...,a_{r})gcd(al,al+1,...,ar)为多少，然后再在map 里面查找对应答案即可.

错因分析：1.没能正确发现对于一个a（<=1e9）他的质因数个数是loga级别的，因为比如2*2*3*5.....=a，则左边至多loga个元素，

巴特西

hdu 5726 GCD GCD+线段树+区间预处理+map

GCD

最新文章

热门文章