分析：（别人写的）

对于所有(l, r)区间，固定右区间，所有(li, r)一共最多只会有log个不同的gcd值，

可以nlogn预处理出所有不同的gcd区间，这样区间是nlogn个，然后对于询问离线处理，

用类似询问区间不同数字的方法，记录每个不同gcd最后出现的位置，然后用树状数组进行维护

 

注：我是看了这段文字会的，但是他的nlogn预处理我不会，我会nlog^2n的

     dp[i][j]代表以i为右端点，向左延伸2^j个点（包括i）的gcd,然后因为这样的gcd满足递减，所以可以二分找区间

代码：

/*RunID: 678021UserID: 96655Submit time: 2016-04-19 23:44:20Language: C++Length: 2378 Bytes.Result: Accepted*/#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;typedef long long LL;const int INF=0x3f3f3f3f;const int N=1e4+5;int T,n,m,dp[N][20];struct ask{  int l,r,id;  bool operator<(const ask &rhs)const{    return r
          
           >1;    int len=pos-mid+1;    int now=pos,cur=-1;    for(int i=13;i>=0;--i){      if(len&(1<
           
            >1;}int hash[35*N],tot,mat[35*N];int res[N*10];int c[N];void add(int x,int t){ for(int i=x;i<=n;i+=i&(-i)) c[i]+=t; }int get(int x){ int ans=0; if(x==0)return 0; for(int i=x;i>0;i-=i&(-i)) ans+=c[i]; return ans;}int main(){ scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) scanf("%d",&dp[i][0]); for(int i=1;i<=m;++i) scanf("%d%d",&p[i].l,&p[i].r),p[i].id=i; for(int k=1;(1<
            
             <=n;++k) for(int i=n;i>1;--i){ int j=i-(1<
             
              0;--j){ int tmp=dp[j][0]; if(last!=-1)tmp=__gcd(tmp,last); last=tmp; ++cnt; seg[cnt].l=j,seg[cnt].r=i,seg[cnt].v=last; hash[++tot]=last; j=erfen(i,last); } } sort(hash+1,hash+1+tot); tot=unique(hash+1,hash+1+tot)-hash-1; sort(p+1,p+1+m); sort(seg+1,seg+1+cnt); memset(mat,0,sizeof(mat)); memset(c,0,sizeof(c)); int now=1; for(int i=1;i<=m;++i){ for(;now<=cnt&&seg[now].r<=p[i].r;++now){ int pos=lower_bound(hash+1,hash+1+tot,seg[now].v)-hash; if(seg[now].l>mat[pos]){ if(mat[pos])add(mat[pos],-1); add(seg[now].l,1); mat[pos]=seg[now].l; } } res[p[i].id]=get(p[i].r)-get(p[i].l-1); } for(int i=1;i<=m;++i) printf("%d\n",res[i]); } return 0;}