分析：找到每一个点的左边离他最近的不互质数，记录下标(L数组)，右边一样如此（R数组），预处理

        这个过程需要分解质因数O（n*sqrt(n))

        然后离线，按照区间右端点排序

        然后扫一遍，对于当前拍好顺序的第i个询问，将所有小于r的点加入更新

        更新的过程是这样的

       （1）对于刚加入点x，树状数组L[x]位置+1   把这个定义为左更新

       （2）对于所有R[i]=x的点，树状数组L[i]位置-1，i位置+1   把这个定义为右更新

       （3）查询是询问区间 l->r的和

 

       时间复杂度分析，因为每个点左更新，右更新各一次，所以单组测试用例是O（nlogn)的

 

       下面来解释为啥这样更新

       查看当前询问 l , r,对于所有小于 l 的点 i，它的所有更新（左更新和右更新）不会影响到树状数组区间 l 到 r 的 和

       对于在l,r区间的点 i，如果 R[i]<=r,那么对于区间 l ->r 有 1 的贡献

                                   如果 R[i]>r,对于这个点，只有左更新L[i]+1;

                                                    如果 L[i]>=l ，对于查询区间有 1 的贡献

                                                    如果 L[i]<l，对于查询区间没有贡献

       不难发现，这样对于查询区间有贡献的点，都是会和别人打架的点

       所以该查询的答案就是  查询区间长度 - 树状数组区间和

       然后以下看代码

    

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;typedef long long LL;const int N=2e5;const LL mod=1e9+7;int a[N+5],c[N+5];int f[N+5],h[N+5],k[N+5];vector
             
              g[N+5];vector
              
               b[N+5];struct Que{ int l,r,id; bool operator<(const Que &e)const { return r
               
                0;x-=(x&(-x))) ans+=c[x]; return ans;}int main(){ for(int i=2; i*i<=N; ++i) { if(vis[i])continue; for(int j=i*i; j<=N; j+=i) vis[j]=1; } for(int i=2; i<=N; ++i) if(!vis[i])prime[cnt++]=i; for(int i=2; i<=N; ++i) { int t=i; for(int j=0; j
                
                 <=i; ++j) { if(t%prime[j])continue; g[i].push_back(prime[j]); while(t%prime[j]==0)t/=prime[j]; if(t==1)break; } if(!vis[t]&&t!=1) g[i].push_back(t); } while(~scanf("%d%d",&n,&m),n) { memset(f,0,sizeof(f)); memset(c,0,sizeof(c)); for(int i=2; i<=n+1; ++i) { scanf("%d",&a[i]); h[i]=1; k[i]=n+2; } for(int i=2; i<=n+1; ++i) { for(int j=0; j
                 
                  1; --i) { for(int j=0; j