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

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

Input

The first line of input contains a number

Output

For each case, you need to output “Case #:t” at the beginning.(with quotes,

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:
",++kk);
        for(int i=1;i<=q;i++)
        {
            int k=query(1,l[i],r[i]);
            printf("%d %lld
",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)$

$1000,000,000的时间内预处理出所有的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)为多少，然后再在map 里面查找对应答案即可.$