【HDU4947】GCD Array (莫比乌斯反演+树状数组)

#include<cstdio>
#include<cstring>
#include<vector>
#define ll long long
#define N 200005
using namespace std;

int miu[N],prime[N],cnt;
ll sum[N],last,lasttemp,temp;
vector<int>fac[N];
bool check[N];
ll ans;
ll getsum(int x){
    ll ans=0;
    for(;x;x-=x&-x)ans+=sum[x];
    return ans;
}
void add(int x,int v){
    for(;x<N;x+=x&-x)sum[x]+=v;
}
void Mobius(){
    miu[1]=1;
    for(int i=2;i<N;i++){
        if(!check[i]){
            prime[cnt++]=i;
            miu[i]=-1;
        }
        for(int j=0;j<cnt;j++){
            if(i*prime[j]>N)break;
            check[i*prime[j]]=1;
            if(i%prime[j])miu[i*prime[j]]=-miu[i];
            else break;
        }
    }
}
int main(){
    int l,m,cas=0;
    Mobius();
    for(int i=1;i<N;i++)
        for(int j=i;j<N;j+=i)
            fac[j].push_back(i);
    while(scanf("%d%d",&l,&m),l,m){
        printf("Case #%d:\n",++cas);
        memset(sum,0,sizeof sum);
        while(m--){
            int n,d,v,x;
            scanf("%d",&n);
            if(n==1){
                scanf("%d%d%d",&n,&d,&v);
                if(n%d)continue;
                n/=d;
                for(int i=0;i<fac[n].size();i++){
                    x=fac[n][i];
                    add(x*d,miu[x]*v);
                }
            }else{
                scanf("%d",&n);
                ans=temp=0;
                for(int i=1;i<=n;i=last+1){
                    last=n/(n/i);
                    lasttemp=temp;
                    temp=getsum(last);
                    ans+=n/i*(temp-lasttemp);
                }
                printf("%lld\n",ans);
            }
        }
    }
}