[BZOJ2693] jzptab (莫比乌斯反演,积性函数,线性筛)

发布于 2018-01-16  7 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ2693] jzptab (莫比乌斯反演,积性函数,线性筛)

Description

BZOJ2693

Http

BZOJ
权限题,提供本站离线版本:bzojch

Tag

莫比乌斯反演,线性筛,积性函数

题目大意

这道题一样,但变成了多组数据。

解决思路

前面的式子到这道题查看,我们直接从那一道题的结尾开始推。
在那道题的最后,我们得到
\[Ans=\sum_{d=1}^{n} d * \sum_{x=1}^{n/d} \mu(x) * x^2 * \sum_{i=1}^{n/d/x} \sum_{j=1}^{m/d/x} ij\]
由于后面是两个等差数列求和,所以我们设\(S(i)=\frac{(i+1)*i}{2}\),那么就有
\[Ans=\sum_{d=1}^{n} d* \sum_{x=1}^{n/d} \mu(x) * x^2 * S(\frac{n}{dx}) * S(\frac{m}{dx})\]
设\(T=x* d\),则
\[Ans=\sum_{d=1}^{n} d* \sum_{x=1}^{n/d} \mu(x) * x^2 * S(\frac{n}{T}) * S(\frac{m}{T})\]
现在我们考虑枚举\(T\),那么因为\(T=x*d\),所以对于每一个\(d|T\),\(d\)都有\(\mu(x)*d*x^2\)的贡献。又因为\(x=\frac{T}{d}\),所以,式子就化为
\[Ans=\sum_{T=1}^{n} S(\frac{n}{T}) * S(\frac{m}{T}) * \sum_{d|T} \mu(d) Td\]
后面这一部分是积性函数,可以线性筛出来的,具体讨论一下。
设\(p\)为质数,设\[f(x)=\sum_{d|T} \mu(d) T*d=T*\sum_{d|T} \mu(d) * d\]
那么就有
\[\begin{cases} f(p)=p*(\mu(1)*1+\mu(p)*p)=p-p^2 \\ f(p*i)=f(p)*f(i) \quad \quad \quad \quad \quad \quad \quad gcd(i,p)==1 \\ f(p*i)=p*f(i) \quad \quad \quad \quad \quad \quad \quad \quad gcd(i,p)==p \end{cases}\]
线性筛出\(f(i)\),求前缀和数论分块,就可以把单次询问的复杂度降到\(O(\sqrt{n})\)

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ2693] jzptab (莫比乌斯反演,积性函数,线性筛)


HNCJ OIer 一枚