HDU - 5869 Different GCD Subarray Query

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 aa of NN positive integers a1,a2,⋯aN−1,aNa1,a2,⋯aN−1,aN; a subarray of aa is defined as a continuous interval between a1a1 and aNaN. In other words, ai,ai+1,⋯,aj−1,ajai,ai+1,⋯,aj−1,aj is a subarray of aa, for 1≤i≤j≤N1≤i≤j≤N. For a query in the form (L,R)(L,R), tell the number of different GCDs contributed by all subarrays of the interval [L,R][L,R]. 
  

Input

There are several tests, process till the end of input. 
   
  For each test, the first line consists of two integers NN and QQ, denoting the length of the array and the number of queries, respectively. NN positive integers are listed in the second line, followed by QQ lines each containing two integers L,RL,Rfor a query. 

You can assume that 
   
    1≤N,Q≤1000001≤N,Q≤100000 
     
   1≤ai≤10000001≤ai≤1000000

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

6
6
6

题意：求给定区间的子区间构成不同gcd的个数

保存以当前位置构成的gcd和左端点，对于查询先离线处理，然后通过树状数组更新，相同gcd保留靠右位置的

至于怎么求gcd  用pair+vector 来保存当前位置的 然后下一个位置通过上一个位置来求

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
#define lowbit(x) (x)&(-x)
const int maxn=1000100;
struct node
{
    int l,r;
    int id;
    bool operator <(const node &x)const {
        return r<x.r;
    }
}b[maxn];
int n,q;
int ans[maxn],sum[maxn],vis[maxn];
vector< pair<int,int> > v[maxn];
void update(int x,int val)
{
	while(x<=1e5)
	{
		sum[x]+=val;
		x+=lowbit(x);
	}
}
int query(int x)
{
	int res=0;
	while(x)
	{
		res+=sum[x];
		x-=lowbit(x);
	}
	return res;
}
int main()
{
    int x,p;
    while(~scanf("%d%d",&n,&q))
    {
    	memset(sum,0,sizeof(sum));
    	memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++)
        {
            v[i].clear();
            //vis[i]=0;
            scanf("%d",&x);
            p=i;
            for(int j=0;j<v[i-1].size();j++)
            {
                int s1=v[i-1][j].first;
                int s2=v[i-1][j].second;
                int d=__gcd(s1,x);
                if(d!=x)
                {
                    v[i].push_back(make_pair(x,p));
                    x=d,p=s2;
                }
            }
            v[i].push_back(make_pair(x,p));
        }
        for(int i=1;i<=q;i++)
        {
            scanf("%d%d",&b[i].l,&b[i].r);
            b[i].id=i;
        }
        sort(b+1,b+1+q);
        int l=1;
        for(int i=1;i<=n;i++)
        {
        	//printf("%d ",vis[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]) update(vis[s1],-1);
                vis[s1]=s2;
                update(s2,1);
            }
            while(l<=q&&b[l].r==i)
            {
                ans[b[l].id]=query(b[l].r)-query(b[l].l-1);
                l++;
            }
        }
        for(int i=1;i<=q;i++)
        printf("%dn",ans[i]);
    }
    return 0;
}

最后

以上就是激情鱼为你收集整理的HDU - 5869 Different GCD Subarray Query的全部内容，希望文章能够帮你解决HDU - 5869 Different GCD Subarray Query所遇到的程序开发问题。

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