题解 P1891 【疯狂LCM】

· · 题解

挺妙的一道题。

要求的是\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 这种算法有点卡，注意能不开`long long`的地方就别开`long long`。