首页 > 代码库 > 【bzoj3529】 Sdoi2014—数表
【bzoj3529】 Sdoi2014—数表
μhttp://www.lydsy.com/JudgeOnline/problem.php?id=3529 (题目链接)
题意
多组询问，每次给出${n,m,a}$。求$${\sum_{i=1}^n\sum_{j=1}^m[\sum_{d|i,d|j}d<=a]\sum_{d|i,d|j}d}$$
Solution
PoPoQQQ的看不懂，我还是比较适合套路→_→：http://blog.csdn.net/FZHvampire/article/details/50964639
有${a}$的限制很不好做，我们不妨先来看看如果没有${a}$的限制，是个什么情况。
\begin{aligned} & \sum_{i=1}^n\sum_{j=1}^m\sum_{d|i,d|j}d \\ =&\sum_{i=1}^n\sum{j=1}^m\sum_{d=1}^{min(n,m)}f(d)[gcd(i,j)=d] \end{aligned}
这里${f(d)}$表示${d}$的约数和，由约数和定理：$${d=p_1^{a_1}p_2^{a_2}p_3^{a_3}······p_k^{a_k}}$$
$${f(d)=(p_1^0+p_1^1+······+p_1^{a_1})(p_2^0+p_2^1+······+p_2^{a_2})······(p_k^0+p_k^1+······+p_k^{a_k})}$$
我们发现当${p,q}$互质时，${f(pq)=f(p)f(q)}$，${f}$是个积性函数。也就是说${f}$可以线性筛求解，具体求法可以看代码。回到上面的问题，我们继续变化这个式子。
\begin{aligned} &\sum_{i=1}^n\sum_{j=1}^m\sum_{d=1}^{min(n,m)}f(d)[gcd(i,j)=d] \\ =&\sum_{d=1}^{min(n,m)}f(d)\sum_{i=1}^{\lfloor{n/d}\rfloor}\sum_{j=1}^{\lfloor{m/d}\rfloor}[gcd(i,j)=1] \\ =&\sum_{d=1}^{min(n,m)}f(d)\sum_{t=1}^{min(\lfloor{n/d}\rfloor,\lfloor{m/d}\rfloor)}μ(t)\lfloor\frac{n}{dt}\rfloor\lfloor\frac{m}{dt}\rfloor \end{aligned}
我们令${Q=dt}$，先枚举${Q}$，得到：$${\sum_{Q=1}^{min(n,m)}\lfloor\frac{n}{Q}\rfloor\lfloor\frac{m}{Q}\rfloor\sum_{d|Q}f(d)μ(\frac{Q}{d})}$$
我们对${f}$和${μ}$函数的狄利克雷卷积${g(Q)=\sum_{d|Q}f(d)μ(\frac{Q}{d})}$预处理前缀和，前面的${\lfloor\frac{n}{Q}\rfloor\lfloor\frac{m}{Q}\rfloor}$分块，那么这个式子的计算就达到了${\sqrt{n}}$。
考虑如何加入限制${a}$。
我们可以离线，将询问按照${a}$从小到大排序，${f}$函数按照从小到大排序。询问的时候，我们就动态维护一个树状数组${c}$。树状数组的每一位${c[x]}$存的是卷积${g(x)}$中${f(d)}$不超过${a}$的数之和。数据组数为${T}$，询问复杂度${O(T\sqrt{n}logn)}$
细节
这题复杂度有点卡，对于取模运算我们可以对${int}$自然溢，最后再${\&2147483647}$就可以了。
代码
// bzoj3994#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<vector>#include<cmath>#define LL long long#define inf 2147483647#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;const int maxn=100010;int mu[maxn],e[maxn],ans[maxn],c[maxn],vis[maxn],p[maxn],t[maxn],g[maxn];struct F {int d,num;}f[maxn];struct Q {int n,m,a,id;}q[maxn];bool cmpT(Q a,Q b) {return a.a<b.a;}bool cmpt(F a,F b) {return a.d<b.d;}int lowbit(int x) {return x&-x;}int power(int a,int b) { int res=1; while (b) { if (b&1) res*=a; a*=a,b>>=1; } return res;}void add(int x,int val) { for (int i=x;i<maxn;i+=lowbit(i)) c[i]+=val;}int query(int x) { int s=0; for (int i=x;i>=1;i-=lowbit(i)) s+=c[i]; return s;}int main() { mu[1]=1;f[1].d=f[1].num=1; for (int i=2;i<maxn;i++) { f[i].num=i; if (!vis[i]) mu[i]=-1,f[i].d=t[i]=1+i,g[i]=1,p[++p[0]]=i; for (int j=1;j<=p[0] && i*p[j]<maxn;j++) { vis[i*p[j]]=1; if (i%p[j]==0) { mu[i*p[j]]=0; g[i*p[j]]=g[i]+1; t[i*p[j]]=t[i]+power(p[j],g[i]+1); f[i*p[j]].d=f[i].d/t[i]*t[i*p[j]]; break; } else { mu[i*p[j]]=-mu[i]; f[i*p[j]].d=f[i].d*f[p[j]].d; g[i*p[j]]=1;t[i*p[j]]=p[j]+1; } } } int T;scanf("%d",&T); for (int i=1;i<=T;i++) scanf("%d%d%d",&q[i].n,&q[i].m,&q[i].a),q[i].id=i; sort(q+1,q+1+T,cmpT); sort(f+1,f+maxn,cmpt); for (int now=0,i=1;i<=T;i++) { while (now<maxn && f[now+1].d<=q[i].a) { now++; for (int j=1;j*f[now].num<maxn;j++) add(j*f[now].num,mu[j]*f[now].d); } int n=q[i].n,m=q[i].m; if (n>m) swap(n,m); for (int j=1,k;j<=n;j=k+1) { k=min(n/(n/j),m/(m/j)); ans[q[i].id]+=(n/j)*(m/j)*(query(k)-query(j-1)); } ans[q[i].id]&=inf; } for (int i=1;i<=T;i++) printf("%d\n",ans[i]); return 0;}
【bzoj3529】 Sdoi2014—数表