题目地址：http://codeforces.com/contest/474/problem/F
由题意可知，最后能够留下来的一定是区间最小gcd。
那就转化成了该区间内与区间最小gcd数相等的个数。区间最小gcd一定小于等于区间最小值。所以仅仅要先推断最小值是否是最小gcd。若是的话，就求出最小值的个数。然后用r-l+1-个数就可以。
对于以上信息。能够用线段树来维护。分别维护区间gcd，区间最小值以及区间最小值的个数。
代码例如以下：
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <set>
#include <algorithm> using namespace std;
#define LL __int64
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
const int INF=0x3f3f3f3f;
const int MAXN=100000;
int minv[MAXN<<2], gcd[MAXN<<2], num[MAXN<<2], q_minv, q_gcd, q_num;
int getgcd(int a, int b)
{
return a==0? b:getgcd(b%a,a);
}
void PushUp(int rt)
{
minv[rt]=min(minv[rt<<1],minv[rt<<1|1]);
gcd[rt]=getgcd(gcd[rt<<1],gcd[rt<<1|1]);
if(minv[rt<<1]==minv[rt<<1|1])
num[rt]=num[rt<<1]+num[rt<<1|1];
else if(minv[rt<<1]>minv[rt<<1|1])
num[rt]=num[rt<<1|1];
else
num[rt]=num[rt<<1];
}
void build(int l, int r, int rt)
{
if(l==r)
{
scanf("%d",&minv[rt]);
num[rt]=1;
gcd[rt]=minv[rt];
return ;
}
int mid=l+r>>1;
build(lson);
build(rson);
PushUp(rt);
}
void query(int ll, int rr, int l, int r, int rt)
{
if(ll<=l&&rr>=r)
{
q_gcd=getgcd(q_gcd,gcd[rt]);
if(minv[rt]==q_minv)
{
q_num+=num[rt];
}
else if(minv[rt]<q_minv)
{
q_num=num[rt];
q_minv=minv[rt];
}
return ;
}
int mid=l+r>>1;
if(ll<=mid) query(ll, rr, lson);
if(rr>mid) query(ll,rr,rson);
}
int main()
{
int n, m, i, l, r;
scanf("%d",&n);
build(1, n, 1);
/*for(i=1;i<=9;i++)
{
printf("%d %d %d\n",minv[i], gcd[i], num[i]);
}*/
scanf("%d",&m);
while(m--)
{
scanf("%d%d",&l,&r);
q_minv=INF;
q_gcd=0;
q_num=0;
query(l,r,1,n,1);
if(q_gcd==q_minv)
{
printf("%d\n",r-l+1-q_num);
}
else
{
printf("%d\n",r-l+1);
}
}
return 0;
}