![]()
1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 #include<algorithm>
5 #include<cmath>
6 using namespace std;
7 const int N=200020;
8 int a[N],n,m,tmp;
9 struct tree{
10 int l,r,gcd,sum;
11 }tr[N*4];
12 int gcd(int x,int y){
13 if(y==0)return x;
14 else return gcd(y,x%y);
15 }
16 void update(int now){
17 int GCD=gcd(tr[now*2].gcd,tr[now*2+1].gcd);
18 tr[now].gcd=GCD;
19 if(tr[now*2].gcd==tr[now*2+1].gcd)tr[now].sum=tr[now*2].sum+tr[now*2+1].sum;
20 else if(tr[now*2].gcd==GCD)tr[now].sum=tr[now*2].sum;
21 else if(tr[now*2+1].gcd==GCD)tr[now].sum=tr[now*2+1].sum;
22 else tr[now].sum=0;
23 }
24 void build(int l,int r,int now){
25 tr[now].l=l;tr[now].r=r;
26 if(l==r){
27 tr[now].gcd=a[l];
28 tr[now].sum=1;
29 return;
30 }
31 int mid=(l+r)>>1;
32 build(l,mid,now*2);
33 build(mid+1,r,now*2+1);
34 update(now);
35 }
36 int getgcd(int l,int r,int now){
37 if(tr[now].l==l&&tr[now].r==r){
38 return tr[now].gcd;
39 }
40 int mid=(tr[now].l+tr[now].r)>>1;
41 if(l>mid)return getgcd(l,r,now*2+1);
42 else if(r<=mid)return getgcd(l,r,now*2);
43 else {
44 return gcd(getgcd(l,mid,now*2),getgcd(mid+1,r,now*2+1));
45 }
46 }
47 int check(int l,int r,int now){
48 if(tr[now].l==l&&tr[now].r==r){
49 if(tr[now].gcd==tmp)return tr[now].sum;
50 else return 0;
51 }
52 int mid=(tr[now].l+tr[now].r)>>1;
53 if(l>mid)return check(l,r,now*2+1);
54 else if(r<=mid)return check(l,r,now*2);
55 else {
56 return check(l,mid,now*2)+check(mid+1,r,now*2+1);
57 }
58 }
59 int main(){
60 while(~scanf("%d",&n)){
61 for(int i=1;i<=n;i++){
62 scanf("%d",&a[i]);
63 }
64 build(1,n,1);
65 scanf("%d",&m);
66 for(int i=1,l,r;i<=m;i++){
67 scanf("%d%d",&l,&r);
68 tmp=getgcd(l,r,1);
69 printf("%d
",r-l+1-check(l,r,1));
70 }
71 }
72 return 0;
73 }
