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\)。
数据范围：\(1\le n,d,v\le2\cdot 10^5,1\le x\le 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}\)加上\(v\cdot \mu (p)\)即可。
2操作，是对\(a_i\)求和：
\]
对于固定的d来说，1~x内\(f_d\)要加\(\lfloor \frac x d\rfloor\)次。再分块加速一下，也就是对于\(\lfloor\frac x d\rfloor\)相同的d，把\(f_d\)区间和求出来再乘上\(\lfloor\frac x d\rfloor\)，设这个区间是[d1,d2]，那么d2=x/(x/d1) (整除)，为什么呢？因为d2是满足\(\frac x d \ge \lfloor \frac x {d1}\rfloor=k\)的最大的整数d，那么\(x\ge d2\cdot k\)，所以\(\frac x k \ge d2\)，也就是d2=\(\lfloor\frac x k\rfloor\)。
这题的时间复杂度：
预处理出1~N的所有因子，\(O(n\sqrt n)\)。
计算莫比乌斯函数，\(O(n)\)。
1操作，因子有\(\sqrt n\)个，增加是\(O(\log n)\)，总的是\(O(m\sqrt n \log n)\)。
2操作，查询\(O(log n)\)，分块\(O(\sqrt n)\)，也是\(O(m\sqrt n \log n)\)。
总的就是\(O(m\sqrt 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:\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);
}
}
}
}
待看的文章：读贾志鹏线性筛有感 (莫比乌斯函数的应用)