题目大意：
给你一个长度为n的序列a与t对区间l和r，问对于每对区间l,r中，有多少个值不能整除全部的区间中的值。
做法：
我们想能整除全部的数有什么样的条件，答案用(r-l+1)减去就可以。
条件：
区间内的所有数都是他的倍数，公约数一定是最大公约数的因数，所以它肯定是区间gcd与区间最小值。
用线段树维护。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,T,a[N];
struct node{
int mi,gcd,cnt;
};
node tree[4*N];
void pushup(int p){
if(tree[p<<1].mi<tree[p<<1|1].mi){
tree[p].mi=tree[p<<1].mi;
tree[p].cnt=tree[p<<1].cnt;
}else if(tree[p<<1].mi>tree[p<<1|1].mi){
tree[p].mi=tree[p<<1|1].mi;
tree[p].cnt=tree[p<<1|1].cnt;
}else{
tree[p].mi=tree[p<<1].mi;
tree[p].cnt=tree[p<<1].cnt + tree[p<<1|1].cnt;
}
tree[p].gcd=__gcd(tree[p<<1].gcd,tree[p<<1|1].gcd);
}
void build(int p,int l,int r){
if(l==r){
tree[p].gcd=tree[p].mi=a[l];
tree[p].cnt=1;
return;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
pushup(p);
}
int query_gcd(int p,int l,int r,int L,int R){
if(L<=l&&r<=R){
return tree[p].gcd;
}
int mid=(l+r)>>1;
int res=0;
if(L<=mid) res=__gcd(res,query_gcd(p<<1,l,mid,L,R));
if(mid<R) res=__gcd(res,query_gcd(p<<1|1,mid+1,r,L,R));
return res;
}
int query_min(int p,int l,int r,int L,int R){
if(L<=l&&r<=R){
return tree[p].mi;
}
int mid=(l+r)>>1;
int res=INT_MAX;
if(L<=mid) res=min(res,query_min(p<<1,l,mid,L,R));
if(mid<R) res=min(res,query_min(p<<1|1,mid+1,r,L,R));
return res;
}
int query_cnt(int p,int l,int r,int L,int R,int k){
if(L<=l&&r<=R){
if(tree[p].mi==k){
return tree[p].cnt;
}
return 0;
}
int mid=(l+r)>>1;
int res=0;
if(L<=mid) res+=query_cnt(p<<1,l,mid,L,R,k);
if(mid<R) res+=query_cnt(p<<1|1,mid+1,r,L,R,k);
return res;
}
int main(){
scanf("%d",&n);
for(int i=1; i<=n; i++){
scanf("%d",&a[i]);
}
build(1,1,n);
scanf("%d",&T);
while(T–){
int l,r;
scanf("%d%d",&l,&r);
int gcd=query_gcd(1,1,n,l,r);
int mi=query_min(1,1,n,l,r);
int cnt=query_cnt(1,1,n,l,r,mi);
printf("%d\\n",(r-l+1)-(gcd==mi ? cnt : 0));
}
return 0;
}
