dtoj2118. GCD Arrays

我似乎粘贴不了题目，一粘贴就卡住。。

Sol.

考虑第一个式子

$ sumlimits_{x} [gcd(x,n)==d] a[x]+=v$   
$ sumlimits_{x} [gcd(x/d,n/d)==1] a[x]+=v$   
$ sumlimits_{x} a[x]+=v*[gcd(x/d,n/d)==1]$   
$ sumlimits_{g|(n/d)} sumlimits_{x} a[x*g*d]+=v*mu(g)$  

考虑一个数的因数最多sqrt个，我们暴力枚举n/d的约数g

$ sumlimits_{g|(n/d)} sumlimits_{(d*g)|t}  a[t]+=v*mu(g)$

那么每次要把一个数的倍数的所有位置加一个值。

这个复杂度过不了，我们设

$a[x]=sumlimits_{d|x}b[d]$

 那么每次只需要单点加b了

查询的时候，我们考虑一段n/x相同的x，这些b[x]会贡献n/x次。

整数分块即可。

效率O（nsqrt(n)log(n)）

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define maxn 400005
using namespace std;
int T,n,q,op,mu[maxn],pri[maxn],tot,flag[maxn];
int nn,d,x;
vector<int>fac[maxn];
long long tree[maxn],v;
void jia(int k,long long val){
    for(int i=k;i<=n;i+=i&-i)tree[i]+=val;
}
long long ask(int k){
    long long sum=0;
    for(int i=k;i;i-=i&-i)sum+=tree[i];
    return sum;
}
int main()
{    
    n=400000;
    mu[1]=1;
    for(int i=2;i<=n;i++){
        if(!flag[i])mu[i]=-1,pri[++tot]=i;
        for(int j=1;j<=tot&&i*pri[j]<=n;j++){
            flag[i*pri[j]]=1;
            if(i%pri[j]==0)break;
            mu[i*pri[j]]=-mu[i];
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j+=i)fac[j].push_back(i);
    while(1){
        T++;
        scanf("%d%d",&n,&q);
        if(!n&&!q)break;
        printf("Case #%d:
",T);
        memset(tree,0,sizeof tree);
        while(q--){
            scanf("%d",&op);
            if(op==1){
                scanf("%d%d%lld",&nn,&d,&v);
                if(nn%d!=0)continue;
                int tmp=nn/d;int sz=fac[tmp].size();
                for(int i=0;i<sz;i++){
                    jia(fac[tmp][i]*d,mu[fac[tmp][i]]*v);
                }
            }
            else {
                scanf("%d",&x);
                int now=1,la=1;
                long long ans=0;
                while(now<=x){
                    la=x/(x/now);
                    ans+=(ask(la)-ask(now-1))*1LL*(x/now);
                    now=la+1;
                }
                printf("%lld
",ans);
            }
        }
    }
    return 0;
}