比赛的时候知道用树状数组，但有点乱不知道怎么处理。
统计不同的gcd的个数其实就是用树状数组统计区间内不同的数的模板题啊...
复杂度O(nlogn)
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N = 1e5+10; 4 int n,q,i,j,a[N],l[N],v[N]; 5 int fun(int x,int y){return __gcd(x,y);} 6 7 struct p{ 8 int l, r, ans, k; 9 }; 10 p query[N]; 11 bool cmp1(const p& a, const p& b){ 12 return a.r < b.r; 13 } 14 bool cmp2(const p& a, const p& b){ 15 return a.k < b.k; 16 } 17 18 int c[N], last[N*10], maxn; 19 int lowbit(int x){ return x&-x;} 20 void add(int x, int d){ 21 for(int i = x; i <= n; i += lowbit(i)) 22 c[i] += d; 23 } 24 int sum(int x){ 25 int ret = 0; 26 while(x){ 27 ret += c[x]; 28 x -= lowbit(x); 29 } 30 return ret; 31 } 32 33 int main(){ 34 while(~scanf("%d%d", &n, &q)){ 35 maxn = -1; 36 for(i = 1; i <= n; i++) scanf("%d", a+i), maxn = max(maxn, a[i]); 37 for(i = 1; i <= q; i++){ 38 scanf("%d%d", &query[i].l, &query[i].r); 39 query[i].k = i; 40 } 41 sort(query+1, query+q+1, cmp1); 42 memset(last, 0, sizeof(int)*(maxn+5)); 43 memset(c, 0, sizeof(int)*(n+5)); 44 45 int qq = 1; 46 for(i = 1; i <= n; i++){ 47 for(v[i] = a[i], j = l[i] = i; j; j = l[j]-1){ 48 v[j] = fun(v[j], a[i]); 49 while(l[j] > 1&&fun(a[i], v[l[j]-1]) == fun(a[i], v[j])) l[j] = l[l[j]-1]; 50 //[l[j]..j,i]区间内的值求fun均为v[j] 51 if(last[ v[j] ]){ 52 if(last[ v[j] ] < j){ 53 add(last[ v[j] ], -1); 54 add(j, 1); 55 last[ v[j] ] = j; 56 } 57 } 58 else{//v[j] 没有 59 add(j, 1); 60 last[ v[j] ] = j; 61 } 62 } 63 while(qq <= q&&query[qq].r == i){ 64 query[qq].ans = sum(query[qq].r) - sum(query[qq].l-1); 65 qq++; 66 } 67 } 68 sort(query+1, query+q+1, cmp2); 69 for(int i = 1; i <= q; i++) 70 printf("%d ", query[i].ans); 71 } 72 }