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

BUPT2017 wintertraining(15) #5H

HDU- 4947

题意

题解

官方题解：

代码

代码语言：javascript复制

#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("%lldn",ans);
            }
        }
    }
}

相似题，待做： SPOJ PGCD - Primes in GCD Table (好题! 莫比乌斯反演＋分块求和优化)

海外加速

0 人点赞