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\n", query[i].ans);71     }72 }