BZOJ3529 : [Sdoi2014]数表（反演+BIT）

本文主要是介绍BZOJ3529 : [Sdoi2014]数表（反演+BIT），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

SDOI真的是什么毒瘤题都有qwq
这个题首先推式子的步骤我就不说了
最后长这个样子：(N<=M) (f(d)代表约数和函数)

$$\sum_{T=1}^N \lfloor\frac N T\rfloor \lfloor\frac M T\rfloor \sum_{d|T}f(d)*\mu(\frac T d)$$ 如果没有a的限制，这样就可以了
我们考虑如何处理那个限制
我们对询问离线，按照a排序
线性筛出来约数和以及莫比乌斯函数
我们按顺序插入每一个f(d)
每次枚举d的倍数计算对前缀和的贡献
树状数组维护前缀和
分块查询答案
要注意自然溢出，不然会TLE
$O(maxn+Q(\sqrt n+\sqrt m)logmaxn)$
代码：

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#define LL long long
using namespace std;
inline int read(){int x=0,f=1;char ch=' ';while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0' && ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return f==1?x:-x;
}
const int N=1e5+5;
int cnt,prime[N],vis[N],f[N],mu[N],g[N];
inline void init(int n){f[1]=1;mu[1]=1;g[1]=1;for(int i=2;i<=n;++i){if(!vis[i]){prime[++cnt]=i;mu[i]=-1;g[i]=1;f[i]=i+1;}for(int j=1;j<=cnt && i*prime[j]<=n;++j){vis[i*prime[j]]=1;if(i%prime[j]==0){mu[i*prime[j]]=0;g[i*prime[j]]=g[i];f[i*prime[j]]=f[i]*prime[j]+f[g[i]];break;}else{mu[i*prime[j]]=-mu[i];g[i*prime[j]]=i;f[i*prime[j]]=f[i]*f[prime[j]];}}}
}
const int Lim=1e5;
int t[N];
inline void add(int x,int v){while(x<=Lim){t[x]+=v;x+=x&-x;}
}
inline int query(int x){int ans=0;while(x){ans+=t[x];x-=x&-x;}return ans;
}
struct Query{int n,m,lim,id;Query(){}inline bool operator < (const Query& b) const {return lim<b.lim;}
}q[N];
struct Insert{int x,v;Insert(){}inline bool operator < (const Insert& b) const {return v<b.v;}
}I[N];
int mxval,num,Ans[N];
int main(){init(1e5);int T=read();for(int i=1;i<=T;++i){q[i].n=read();q[i].m=read();q[i].lim=read();q[i].id=i;mxval=max(mxval,q[i].lim);}sort(q+1,q+T+1);for(int i=1;i<=Lim;++i){if(f[i]<=mxval){I[++num].x=i;I[num].v=f[i];}}sort(I+1,I+num+1);int now=1;I[num+1].v=0x3f3f3f3f;for(int s=1;s<=T;++s){while(I[now].v<=q[s].lim){int p=I[now].x;for(int i=1;i*p<=Lim;++i){add(i*p,I[now].v*mu[i]);}now++;}int n=q[s].n,m=q[s].m;if(n>m)swap(n,m);int ans=0;for(int i=1,j=0;i<=n;i=j+1){j=min(n/(n/i),m/(m/i));ans+=(n/i)*(m/i)*(query(j)-query(i-1));}Ans[q[s].id]=ans;}for(int i=1;i<=T;++i){Ans[i]&=2147483647;printf("%d\n",Ans[i]);}return 0;
}

这篇关于BZOJ3529 : [Sdoi2014]数表（反演+BIT）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---