题目大意：

给出m个查询，查询出[ l - r] 之间去 这个区间所有的数都互质的数有多少个。

思路分析：

首先我们处理出来每一个位置，左边和右边第一个与之不互质的数的位置。记在pre 和 next下。这个方法用分解质因数就好。

一个区间内的答案，等于这个区间的所有数减去有与之互质数的个数。

现在要统计的就是

1.对于一个给定的查询[l,r] 区间，统计有多少个 i （l<= i <=r） 的pre[i] 或 next[i]在[l,r]内。

2.对于一个给定的查询[l,r]区间，统计有多个个i （l<= i < = r）的pre[i] 且 next[i] 在[l,r]内。

那么区间的答案就是 r-l+1-（统计出来的1的答案）+（统计出来的2的答案）。

对于统计2，我们就是判断有多个[pre[i],next[i] ] 在 [l,r]内。

对于统计1，我们可以用判断 [pre[i],i] 或 [i,next[i]]来替换。

#include 
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #define lowbit(x) (x&(-x)) #define maxn 200005 #define lson num<<1,s,mid #define rson num<<1|1,mid+1,e using namespace std; bool vis[200005]; int prime[50000],top_prime; int n,m; struct foo { int s,e; int index,ans; foo(){} foo(int st,int ed,int id):s(st),e(ed),index(id){} bool operator < (const foo &cmp)const { return e
        
         =1;x-=lowbit(x))ans+=bit[x]; for(int x=l-1;x>=1;x-=lowbit(x))ans-=bit[x]; return ans; } void sieve(int n) { int m=(int)sqrt(n+0.5); memset(vis,0,sizeof(vis)); for(int i=2;i<=m;i++) { if(!vis[i]) { for(int j=i*i;j<=n;j+=i) vis[j]=1; } } for(int i=2;i<=m;i++) { if(vis[i]==0) prime[top_prime++]=i; } } int pre[200005],next[200005],now[200005],a[200005],tnext[200005]; vector
         
           p[200005]; vector 
          
            ret[3]; int ans[3][maxn]; void getans(int key) { memset(bit,0,sizeof bit); int ind=0; for(int i=1;i<=m;i++) { while(ind
           
            1) p[a[i]].push_back(tmp); } memset(now,0,sizeof(now)); for(int i=1;i<=n;i++) { for(int j=0;j