自动搬运

查看原文

来自洛谷，原作者为

	YLWang 别等到一千年以后 所有人都遗忘了我

搬运于2025-08-24 21:58:01，当前版本为作者最后更新于2020-03-21 10:26:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

请务必在博客中查看

莫比乌斯反演与杜教筛详解可以见我的博客。非常详细，大家可以来围观围观。

---

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