題目連結：
http://acm.hdu.edu.cn/showproblem.php?pid=5869
Different GCD Subarray Query
Time Limit: 6000/3000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
#### 問題描述
> 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].
輸入
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.
You can assume that
1≤N,Q≤100000
1≤ai≤1000000
輸出
For each query, output the answer in one line.
樣例輸入
5 3
1 3 4 6 9
3 5
2 5
1 5
樣例輸出
6
題意
給你n個數排成一行，每次詢問求一段區間内的所有子串的不同的gcd的種數有多少。
題解
首先，要處理出所有的子區間是比較困難的，而且事實上很多子區間的gcd都是重複出現的，我們把區間右端點固定，那麼随着左區間從右往左移，區間gcd的值成倍遞減，是以我們取到的不同的gcd的值隻有logAi種，處理出來之後，我們就可以用離線的方式，用線段樹來求區間不同的值有幾個，每個事件(處理出來的sigma(logA[i])個區間gcd)以左端點為準插入樹狀數組中維護一下（離線查詢的線段樹/樹狀數組可以參考[這個])。
代碼
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<ctime>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define X first
#define Y second
#define mkp make_pair
#define lson (o<<1)
#define rson ((o<<1)|1)
//#define mid (l+(r-l)/2)
#define sz() size()
#define pb(v) push_back(v)
#define all(o) (o).begin(),(o).end()
#define clr(a,v) memset(a,v,sizeof(a))
#define bug(a) cout<<#a<<" = "<<a<<endl
#define rep(i,a,b) for(int i=a;i<(b);i++)
#define scf scanf
#define prf printf
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef vector<pair<int,int> > VPII;
const int INF=0x3f3f3f3f;
const LL INFL=0x3f3f3f3f3f3f3f3fLL;
const double eps=1e-8;
const double PI = acos(-1.0);
//start----------------------------------------------------------------------
const int maxn=1e5+10;
const int maxa=1e6+10;
int gcd(int a,int b) {
return b==0?a:gcd(b,a%b);
}
struct Node {
int l,r,v;
Node(int l,int r,int v):l(l),r(r),v(v) {}
};
bool cmp1(const Node& t1,const Node& t2) {
return t1.r<t2.r;
}
int n,m;
int arr[maxn],ans[maxn];
int dp[maxn][20];
void rmq_init() {
for(int i=1; i<=n; i++) dp[i][0]=arr[i];
for(int j=1; (1<<j)<=n; j++) {
for(int i=1; i+(1<<j)-1<=n; i++) {
dp[i][j]=gcd(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
}
}
int query(int l,int r) {
int k=0;
while(l+(1<<k)-1<=r) k++;
k--;
return gcd(dp[l][k],dp[r-(1<<k)+1][k]);
}
int sumv[maxn],mp[maxa];
void add(int x,int v) {
while(x<maxn) {
sumv[x]+=v;
x+=(-x)&x;
}
}
int sum(int x) {
int ret=0;
while(x>0) {
ret+=sumv[x];
x-=x&(-x);
}
return ret;
}
void init(){
clr(mp,0);
clr(sumv,0);
}
int main() {
while(scf("%d%d",&n,&m)==2&&n) {
init();
for(int i=1; i<=n; i++) scanf("%d",&arr[i]);
rmq_init();
//v表示區間的gcd.
//處理出代表性的事件
vector<Node> events;
for(int i=1; i<=n; i++) {
int r=i;
while(r>0) {
int l=0,v=query(r,i);
events.pb(Node(r,i,v));
while(l+1<r) {
int mid=l+(r-l)/2;
int tmp=query(mid,i);
if(tmp==v) r=mid;
else l=mid;
}
r--;
}
}
//v表示查詢的id
vector<Node> que;
for(int i=0; i<m; i++) {
int l,r;
scf("%d%d",&l,&r);
que.pb(Node(l,r,i));
}
sort(all(que),cmp1);
sort(all(events),cmp1);
//離線處理
int j=0;
rep(i,0,que.sz()) {
while(j<events.sz()&&events[j].r<=que[i].r){
Node& e=events[j];
if(mp[e.v]){
add(mp[e.v],-1);
}
add(e.l,1);
mp[e.v]=e.l;
j++;
}
ans[que[i].v]=sum(que[i].r)-sum(que[i].l-1);
}
rep(i,0,m) prf("%d\n",ans[i]);
}
return 0;
}
//end-----------------------------------------------------------------------