首页 > > 程序设计 > C/C++ >

2016 大连网赛---Different GCD Subarray Query(…

2018-06-17 23:47:19来源：未知阅读 ()

题目链接

http://acm.split.hdu.edu.cn/showproblem.php?pid=5869

Problem Description

This is a simple problem. The teacher gives Bob a list of problems about GCD (Greatest Common Divisor). After studying some of them, Bob thinks that GCD is so interesting. One day, he comes up with a new problem about GCD. Easy as it looks, Bob cannot figure it out himself. Now he turns to you for help, and here is the problem:

Given an array

Input

There are several tests, process till the end of input.

For each test, the first line consists of two integers

Output

For each query, output the answer in one line.

Sample Input

5 3

1 3 4 6 9

3 5

2 5

1 5

Sample Output

Source

2016 ACM/ICPC Asia Regional Dalian Online

Recommend

wange2014 | We have carefully selected several similar problems for you: 5877 5876 5874 5873 5872

题意：输入N和Q，表示有N个数的一个序列，Q次询问，每次输入 l 和 r 表示一个区间，求这个区间不同的最大公倍数的个数（由这个区间的子区间得到）；

思路：对数列进行GCD离散处理（~我也是才知道还有这样的离散~）

for(int i=1;i<=N;i++)
        {
            int tot=a[i],pos=i;
            for(int j=0;j<v[i-1].size();j++)
            {
                int  r=__gcd(a[i],v[i-1][j].first);
                if(tot!=r)
                {
                   v[i].push_back(make_pair(tot,pos));
                   tot=r;  pos=v[i-1][j].second;
                }
            }
            v[i].push_back(make_pair(tot,pos));
        }

然后对Q次询问离线处理，先输入Q次询问的区间，然后按右端点从小到大排序，i从1~N循环，当i==node[len].r 则 ans[node[len].id]=Sum(i)-Sum(node[len].l-1) ;

可以方便快速的用树状数组处理；

代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
using namespace std;
int a[100005];
int c[1000005];
int vis[1000005];
int sum[100005];
struct Node
{
    int l,r;
    int id;
}node[100005];
bool cmp(const Node s1,const Node s2)
{
    return s1.r<s2.r;
}
vector<pair<int,int> > v[100005];

int __gcd(int x,int y)
{
    int r=x%y;
    x=y;
    y=r;
    if(r==0) return x;
    return __gcd(x,y);
}
int Lowbit(int t)
{
    return t&(t^(t-1));
}
int Sum(int x)
{
    int sum = 0;
    while(x > 0)
    {
        sum += c[x];
        x -= Lowbit(x);
    }
    return sum;
}
void add(int li,int t)
{
    while(li<=1000005)
    {
        c[li]+=t;
        li=li+Lowbit(li);
    }
}
int main()
{
    int N,Q;
    while(scanf("%d%d",&N,&Q)!=EOF)
    {
        for(int i=1;i<=N;i++) scanf("%d",&a[i]);
        for(int i=1;i<=N;i++)
        {
            int tot=a[i],pos=i;
            for(int j=0;j<v[i-1].size();j++)
            {
                int  r=__gcd(a[i],v[i-1][j].first);
                if(tot!=r)
                {
                   v[i].push_back(make_pair(tot,pos));
                   tot=r;  pos=v[i-1][j].second;
                }
            }
            v[i].push_back(make_pair(tot,pos));
        }

        for(int i=0;i<Q;i++)
            scanf("%d%d",&node[i].l,&node[i].r),node[i].id=i;
        sort(node,node+Q,cmp);
        memset(c,0,sizeof(c));
        memset(vis,0,sizeof(vis));
        int len=0;
        for(int i=1;i<=N;i++)
        {
            for(int j=0;j<v[i].size();j++)
            {
                int s1=v[i][j].first;
                int s2=v[i][j].second;
                if(vis[s1]){
                    add(vis[s1],-1);
                }
                vis[s1]=s2;
                add(s2,1);
            }
            while(node[len].r==i)
            {
                sum[node[len].id]=Sum(i)-Sum(node[len].l-1);
                len++;
            }
        }
        for(int i=0;i<Q;i++)
            printf("%d\n",sum[i]);
        for(int i=0;i<=N;i++)
            v[i].clear();
    }
    return 0;
}