链接：http://acm.hdu.edu.cn/showproblem.php?pid=6102

题解：

分析：有点难想。。首先逐个加入右端点，每加入一个，枚举倍数，和题解做法一样，然后更新每个Ai位置的值，当某个区间右端点恰好的刚刚枚举完的右端点时，这时候更新答案，对应询问的答案就是这个时候的区间和，用树状数组处理一下，可以先把询问按右端点从小到大排序，方便查找右端点恰好达到的区间。

然后求互质个数的容斥，具体来说，首先预处理出1~1e5的数的因子和莫比乌斯函数，然后把右端点的倍数，从右往左扫，每加入一个新的，把它分解，然后查找它后面是某个因子倍数的数个数，容斥一下，再更新一下倍数的个数，更新一下该点的答案，继续往左扫，做完以后把个数清空，再做下一次的。可以做一个剪枝，直接把因子对应莫比乌斯函数为0的不放入预处理的数组中。

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 using namespace std;  7 typedef long long ll;  8 const int maxn=1e5+5;  9 int pri[maxn],len=0,mu[maxn]; 10 bool Is_pri[maxn]; 11 vector
          
            factor[maxn]; 12 int n,m,a[maxn],l[maxn],r[maxn],order[maxn],loca[maxn]; 13 ll ans[maxn]; 14 int temp[maxn],num[maxn],cnt=0; 15 bool Cmp(int a,int b){ return r[a]
           
            n=n; 22 memset(c,0,sizeof(c)); 23 } 24 void add(int k,ll num){ 25 while(k<=n){ 26 c[k]+=num; 27 k+=k&-k; 28 } 29 } 30 ll query(int k){ 31 ll sum=0; 32 while(k){ 33 sum+=c[k]; 34 k-=k&-k; 35 } 36 return sum; 37 } 38 ll query(int l,int r){ return query(r)-query(l-1);} 39 }ta; 40 void CalPri(){ 41 mu[1]=1; 42 memset(Is_pri,-1,sizeof(Is_pri)); 43 for(int i=2;i
            
             =0;j--){ 95 int t=temp[j],s=a[t]/a[i]; 96 ll sum=cnt-j-1; 97 for(int k=0;k
             
              =0;j--){105 int t=temp[j],s=a[t]/a[i];106 for(int k=0;k