BUPT2017 wintertraining(15) #5H
题意
有一个长度为l的数组，现在有m个操作，第1种为1 n d v,给下标x 满足gcd(x,n)=d的(a_x)增加v。第2种为2 x,查询(sum_{i=1}^x a_i)。
数据范围：(1le n,d,vle2cdot 10^5,1le xle l)
题解
设(f_i)满足(a_i=sum_{d|i} f_d)，用树状数组存储(f_i)的前缀和。
根据莫比乌斯函数（关于莫比乌斯反演可以看这篇论文：贾志鹏线性筛法与积性函数）的性质，我们知道(sum_{d|n}mu(d)=[n=1])，(这个d和上面的d不是同一个,下面换为p表示) 因此
于是对于给定的n和d，(frac n d)的因子p的d倍就是符合条件的下标x的一个因子。
莫比乌斯反演可得：
(f(n)=sum_{d|n}mu(frac n d)a(n))
因此(f_{pd}=sum mu(p)a(pd))，于是对于1操作，我们只要给(f_{pd})加上(vcdot mu (p))即可。
2操作，是对(a_i)求和：
对于固定的d来说，1~x内(f_d)要加(lfloor frac x d floor)次。再分块加速一下，也就是对于(lfloorfrac x d floor)相同的d，把(f_d)区间和求出来再乘上(lfloorfrac x d floor)，设这个区间是[d1,d2]，那么d2=x/(x/d1) (整除)，为什么呢？因为d2是满足(frac x d ge lfloor frac x {d1} floor=k)的最大的整数d，那么(xge d2cdot k)，所以(frac x k ge d2)，也就是d2=(lfloorfrac x k floor)。
这题的时间复杂度：
预处理出1~N的所有因子，(O(nsqrt n))。
计算莫比乌斯函数，(O(n))。
1操作，因子有(sqrt n)个，增加是(O(log n))，总的是(O(msqrt n log n))。
2操作，查询(O(log n))，分块(O(sqrt n))，也是(O(msqrt n log n))。
总的就是(O(msqrt n log n))
官方题解：
代码
#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:
",++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
",ans);
}
}
}
}
待看的文章：读贾志鹏线性筛有感 (莫比乌斯函数的应用)