HDU-6102 GCDispower

HDU-6102 GCDispower

给定一个的一个排列，有个查询。
每次询问输出

离线处理,对于每次的询问,等价于求.

可以考虑枚举，讲右端点固定，那么对于这个区间中，所有的后

互相互质的对数乘，就是对左端点，所有区间的贡献。

将的倍数且位置小于的数筛出来后，考虑从大到小枚举，每次求与中互质的个数乘

也就是

是从大到小扫过之后整除的个数。利用树状数组区间修改，最后查询每个的值就行。

#include<bits/stdc++.h>
using namespace std;
#define IN freopen("in.txt","r",stdin);
const int N=1e5+5;
typedef long long ll;
int T,n,m;
int p[N],pos[N];
int mu[N]={0,1},num[N]={0};
vector<int>fac[N];
vector<pair<int,int> >R[N];
ll ans[N],sum[N];
void up(int x,ll val){for(int i=x;i<=n;i+=i&-i)sum[i]+=val;}
ll Q(int x){
    ll res=0;
    for(int i=x;i;i&=i-1)res+=sum[i];
    return res;
}
void pre(){
    for(int i=1;i<N;i++){
        fac[i].push_back(i);
        for(int j=i+i;j<N;j+=i){
            if(mu[i])fac[j].push_back(i);
            mu[j]-=mu[i];
        }
    }
}
int main(){
    pre();
    cin>>T;while(T--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)scanf("%d",&p[i]),pos[p[i]]=i,sum[i]=0,R[i].clear();
        for(int i=1;i<=m;i++){
            int l,r;
            scanf("%d%d",&l,&r);
            R[r].push_back({l,i});
        }
        for(int i=1;i<=n;i++){
            vector<int>index;
            for(int j=2*p[i];j<=n;j+=p[i]){
                if(pos[j]<i){
                    index.push_back(pos[j]);
                }
            }
            sort(index.begin(),index.end());
            int sz=index.size();
            for(int j=sz-1;j>=0;j--){
                int x=0,d=p[index[j]]/p[i];
                int t=fac[d].size();
                for(int k=0;k<t;k++){
                    int val=fac[d][k];
                    x+=mu[val]*(num[val]++);
                }
                up(1,1LL*x*p[i]);up(index[j]+1,-1LL*x*p[i]);
            }
            int tz=R[i].size();
            for(int j=0;j<tz;j++){
                ans[R[i][j].second]=Q(R[i][j].first);
            }
            for(int j=sz-1;j>=0;j--){
                int d=p[index[j]]/p[i],t=fac[d].size();
                for(int k=0;k<t;k++)num[fac[d][k]]--;
            }
        }
        for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);
    }
}