题目链接：http://codeforces.com/contest/474/problem/F
题意简而言之就是问你区间l到r之间有多少个数能整除区间内除了这个数的其他的数，然后区间长度减去数的个数就是答案。
要是符合条件的话，那这个数的大小一定是等于gcd(a[l]...a[r])。
我们求区间gcd的话，既可以利用线段树性质区间递归下去然后返回求解，但是每次查询是log的，所以还可以用RMQ，查询就变成O(1)了。
然后求解区间内有多少个数的大小等于gcd的话，也是利用线段树的性质，区间递归求解之，复杂度也是log的。
//#pragma comment(linker, "/STACK:102400000, 102400000")
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
typedef long long LL;
typedef pair <int, int> P;
const int N = 1e5 + ;
int gcd[N][];
struct SegTree {
int l , r , Min , num;
}T[N << ]; int GCD(int a, int b) {
return b ? GCD(b, a % b) : a;
} void ST(int n) {
for(int k = ; k < ; ++k) {
for(int i = ; i + ( << k) - <= n; ++i) {
gcd[i][k] = GCD(gcd[i][k - ], gcd[i + ( << (k - ))][k - ]);
}
}
} void build(int p , int l , int r) {
int mid = (l + r) >> ;
T[p].l = l , T[p].r = r , T[p].num;
if(l == r) {
T[p].Min = gcd[l][];
T[p].num = ;
return ;
}
build(p << , l , mid);
build((p << )| , mid + , r);
if(T[p << ].Min == T[(p << )|].Min) {
T[p].Min = T[p << ].Min;
T[p].num = T[p << ].num + T[(p << )|].num;
}
else if(T[p << ].Min < T[(p << )|].Min) {
T[p].Min = T[p << ].Min;
T[p].num = T[p << ].num;
}
else {
T[p].Min = T[(p << )|].Min;
T[p].num = T[(p << )|].num;
}
} int query(int p , int l , int r , int g) {
int mid = (T[p].l + T[p].r) >> ;
if(T[p].l == l && T[p].r == r) {
return T[p].Min == g ? T[p].num : ;
}
if(r <= mid) {
return query(p << , l , r , g);
}
else if(l > mid) {
return query((p << )| , l , r , g);
}
else {
return query(p << , l , mid , g) + query((p << )| , mid + , r , g);
}
} int main()
{
int n, q, l, r;
scanf("%d", &n);
for(int i = ; i <= n; ++i)
scanf("%d", &gcd[i][]);
ST(n);
build( , , n);
scanf("%d", &q);
while(q--) {
scanf("%d %d", &l, &r);
int k = log2(r - l + );
int g = GCD(gcd[l][k], gcd[r - ( << k) + ][k]);
printf("%d\n", r - l + - query( , l , r , g));
}
return ;
}