题目链接
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 a of N positive integers a1,a2,⋯aN−1,aN; a subarray of a is defined as a continuous interval between a1 and aN. In other words, ai,ai+1,⋯,aj−1,aj is a subarray of a, for 1≤i≤j≤N. For a query in the form (L,R), tell the number of different GCDs contributed by all subarrays of the interval [L,R].
Given an array a of N positive integers a1,a2,⋯aN−1,aN; a subarray of a is defined as a continuous interval between a1 and aN. In other words, ai,ai+1,⋯,aj−1,aj is a subarray of a, for 1≤i≤j≤N. For a query in the form (L,R), tell the number of different GCDs contributed by all subarrays of the interval [L,R].
Input
There are several tests, process till the end of input.
For each test, the first line consists of two integers N and Q, denoting the length of the array and the number of queries, respectively. N positive integers are listed in the second line, followed by Q lines each containing two integers L,R for a query.
For each test, the first line consists of two integers N and Q, denoting the length of the array and the number of queries, respectively. N positive integers are listed in the second line, followed by Q lines each containing two integers L,R for a query.
You can assume that
1≤N,Q≤100000
1≤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
Source
Recommend
题意：输入N和Q，表示有N个数的一个序列，Q次询问，每次输入 l 和 r 表示一个区间，求这个区间不同的最大公倍数的个数（由这个区间的子区间得到）；
思路：对数列进行GCD离散处理（~我也是才知道还有这样的离散~）
for(int i=;i<=N;i++)
{
int tot=a[i],pos=i;
for(int j=;j<v[i-].size();j++)
{
int r=__gcd(a[i],v[i-][j].first);
if(tot!=r)
{
v[i].push_back(make_pair(tot,pos));
tot=r; pos=v[i-][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[];
int c[];
int vis[];
int sum[];
struct Node
{
int l,r;
int id;
}node[];
bool cmp(const Node s1,const Node s2)
{
return s1.r<s2.r;
}
vector<pair<int,int> > v[]; int __gcd(int x,int y)
{
int r=x%y;
x=y;
y=r;
if(r==) return x;
return __gcd(x,y);
}
int Lowbit(int t)
{
return t&(t^(t-));
}
int Sum(int x)
{
int sum = ;
while(x > )
{
sum += c[x];
x -= Lowbit(x);
}
return sum;
}
void add(int li,int t)
{
while(li<=)
{
c[li]+=t;
li=li+Lowbit(li);
}
}
int main()
{
int N,Q;
while(scanf("%d%d",&N,&Q)!=EOF)
{
for(int i=;i<=N;i++) scanf("%d",&a[i]);
for(int i=;i<=N;i++)
{
int tot=a[i],pos=i;
for(int j=;j<v[i-].size();j++)
{
int r=__gcd(a[i],v[i-][j].first);
if(tot!=r)
{
v[i].push_back(make_pair(tot,pos));
tot=r; pos=v[i-][j].second;
}
}
v[i].push_back(make_pair(tot,pos));
} for(int i=;i<Q;i++)
scanf("%d%d",&node[i].l,&node[i].r),node[i].id=i;
sort(node,node+Q,cmp);
memset(c,,sizeof(c));
memset(vis,,sizeof(vis));
int len=;
for(int i=;i<=N;i++)
{
for(int j=;j<v[i].size();j++)
{
int s1=v[i][j].first;
int s2=v[i][j].second;
if(vis[s1]){
add(vis[s1],-);
}
vis[s1]=s2;
add(s2,);
}
while(node[len].r==i)
{
sum[node[len].id]=Sum(i)-Sum(node[len].l-);
len++;
}
}
for(int i=;i<Q;i++)
printf("%d\n",sum[i]);
for(int i=;i<=N;i++)
v[i].clear();
}
return ;
}