题解 P4240 【毒瘤之神的考验】
YLWang
·
·
题解
请务必在博客中查看
莫比乌斯反演与杜教筛详解可以见我的博客。非常详细，大家可以来围观围观。
P4240 毒瘤之神的考验
\begin{aligned}
\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m} \varphi(ij)
&= \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m} \frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))}
\\&= \sum\limits_{d=1}^{n}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m} \frac{\varphi(i)\varphi(j)d[\gcd(i,j)=d]}{\varphi(d)}
\\&= \sum\limits_{d=1}^{n}\frac{d}{\varphi(d)}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m }\varphi(i)\varphi(j)[\gcd(i,j)=d]
\\&= \sum\limits_{d=1}^{n}\frac{d}{\varphi(d)}\sum_{t=1}^{\lfloor\frac{n}{d}\rfloor}\mu(t)\cdot \sum\limits_{i=1}^{\lfloor\frac{n}{dt}\rfloor }\sum\limits_{j=1}^{\lfloor\frac{m}{dt}\rfloor }\varphi(idt)\varphi(jdt)
\\&= \sum\limits_{d=1}^{n}\frac{d}{\varphi(d)}\sum_{t=1}^{\lfloor\frac{n}{d}\rfloor}\mu(t)\cdot \sum\limits_{i=1}^{\lfloor\frac{n}{dt}\rfloor }\sum\limits_{j=1}^{\lfloor\frac{m}{dt}\rfloor }\varphi(idt)\varphi(jdt)
\\&= \sum\limits_{k=1}^{n}\sum\limits_{d|k} \frac{d\cdot\mu(\frac{k}{d})}{\varphi(d)} \sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor }\varphi(ik)\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor }\varphi(jk)
\end{aligned}
令
\begin{aligned}
f(n) = \sum\limits_{d|n} \frac{d\cdot\mu(\frac{k}{d})}{\varphi(d)}
\end{aligned}
则可以套路地枚举倍数预处理出来。这一部分的复杂度是 O(n \operatorname{ln} n).
再令
\begin{aligned}
g(k, n) = \sum\limits_{i=1}^{n}\varphi(ik)
\end{aligned}
我们有递推式
\begin{aligned}
g(i, j) = g(i, j-1) +\varphi(ij)
\end{aligned}
因为k\cdot n \leqslant 10^5, 所以这一部分的复杂度为 O(n \operatorname{ln} n).
我们把原式用 f 与 g 代入。
\begin{aligned}
\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m} \varphi(ij)
&=\sum\limits_{k=1}^{n}f(k)\cdot g(k, \lfloor\frac{n}{k}\rfloor )\cdot g(k,\lfloor\frac{m}{k}\rfloor )
\end{aligned}
然后你会发现这个时候 g 里面是带 k 的不能整除分块。
还是很套路的把整个式子用参数表示出来。令：
\begin{aligned}
t(a, b,n) = \sum\limits_{k=1}^{n}f(k)\cdot g(k, a)\cdot g(k, b)
\end{aligned}
那么最终的结果就是一个差分形式（其实 l 和 r 是整除分块的两端。）
\begin{aligned}
\sum\limits_{\lfloor\frac{n}{l}\rfloor = \lfloor\frac{n}{r}\rfloor \& \lfloor\frac{m}{l}\rfloor = \lfloor\frac{m}{r}\rfloor} t(\lfloor\frac{n}{r}\rfloor, \lfloor\frac{m}{r}\rfloor,r) - t(\lfloor\frac{n}{r}\rfloor, \lfloor\frac{m}{r}\rfloor,l)
\end{aligned}
那么问题就是如何求出 t 数组了。容易发现直接全部预处理会 T 到原地升天。
我们发现这实际上是一个预处理和查询的平衡，所以引出根号分治那一套理论。
因为我们发现，l 和 r 越大，相同一段长度就越大，暴力的复杂度就相对越劣（意思就是用整除分块处理越快）。我们考虑在 l 和 r 较小的时候暴力，否则预处理。
我们设一个阈值 S，将所有 t(1,1,1) - t(S,S,n) 的 t 值预处理出来。
预处理的式子就是
t(j,k,i)=t(j,k,i-1) + f(i)\cdot g(i, j)\cdot g(i, k)
然后查询的时候，对于所有 \lfloor\dfrac{n}{r}\rfloor \leqslant S 可以直接查询。否则，可得知 r \leqslant \lfloor\dfrac{n}{S}\rfloor。 这个时候就可以暴力计算了.
总的复杂度 O(n \ln n + nB^2 + T(\sqrt{n} +\dfrac{n}{B}))。 至于如何调整 B 参照 Ynoi。
这个题真的是一个好题，可谓是推式子与平衡思想结合的极致。
代码链接：https://www.luogu.com.cn/paste/fk563xya