自动搬运

查看原文

来自洛谷，原作者为

	pufanyi pufanyi.github.io

搬运于2025-08-24 21:31:34，当前版本为作者最后更新于2018-06-13 20:26:59，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

挺妙的一道题。

要求的是$\sum_{i=1}^{n}lcm(i, n)$，一看好像没什么思路（可能是本人菜）。当然只会想到暴力打表和看题解了……????

首先这步应该地球人都会去试：

$$\sum_{i=1}^{n}lcm(i, n) = n \sum_{i=1}^{n}\frac{i}{\gcd(i, n)} $$

然后很关键的一步是添一个$\sum$（说一句废话），式子就变成了：

$$n\sum_{d\mid n}\sum_{i=1}^{n}\frac{i}{d}[d=\gcd(i, n)] $$

中括号里是一个类似布尔型的变量。

对于中括号里的式子，两边同除以$d$：

$$n\sum_{d\mid n}\sum_{i=1}^{n}\frac{i}{d}[\gcd(\frac{i}{d}, \frac{n}{d}) = 1] $$

把$\frac{i}{d}$变成$i$，得到：

$$n\sum_{d\mid n}\sum_{i=1}^{\frac{n}{d}}i[\gcd(i, \frac{n}{d}) = 1] $$

把$d$倒着枚举，我们就得到了酱紫的东西：

$$n\sum_{d\mid n}\sum_{i=1}^{d}i[\gcd(i,d) = 1]$$

然后我们来看$\sum_{i=1}^{d}i[\gcd(i,d) = 1]$：与$d$互质的所有数之和。

如果是个数就好求了……

等等，个数？我们是否可以从个数出发？

想一想，对于$\gcd(i, d) = 1$，$\gcd(d-i, d)$是什么？显然也是$1$。

所以$i$是成对出现的（$d=1$除外）。

于是我们发现（当$d \not= 1$时）：

$$\sum_{i=1}^{d}i[\gcd(i,d) = 1] = \frac{\varphi(d)}{2} d $$

$O(n)$预处理$\varphi$，对于每次询问$O(\sqrt{n})$枚举$d$回答。

这种算法有点卡，注意能不开long long的地方就别开long long。