gcd求和

假设您的柿子是这样：

$$\sum \sum \gcd(i,j)$$

欧拉函数的方法

可以用$\varphi \times 1 = n$来代上面的柿子：

$$\sum \sum \sum_{d|\gcd(i,j)}\varphi(d)$$
然后改变枚举顺序。考虑枚举$d$，柿子变成：
$$\sum_d \varphi(d) \sum\sum[d | \gcd(i,j)]$$

显然$\sum\sum[d | \gcd(i,j)] = \lfloor \frac{n}{d} \rfloor\lfloor \frac{m}{d} \rfloor$.

故柿子最终可以表示为：

$$\sum_d \varphi(d) \lfloor \frac{n}{d} \rfloor\lfloor \frac{m}{d} \rfloor$$

换个方向，我们考虑用莫比乌斯反演来干这件事情。

莫比乌斯反演的方法

我们要求的是：

$$\sum \sum \gcd(i,j)$$

不妨枚举$\gcd (i,j) = d$.柿子化为：

$$\sum_d d* \sum\sum[\gcd(i,j) == d]$$

不妨令$f(d) = \sum\sum[\gcd(i,j) == d]$.
则构造$F(d) = \sum\sum[d|\gcd(i,j)]=\lfloor \frac{n}{d} \rfloor\lfloor \frac{m}{d} \rfloor$.

反演得：

$$f(d) = \sum_{d|k}\mu(\frac{k}{d})F(k) = \sum_{d|k}\mu(\frac{k}{d})\lfloor \frac{n}{k} \rfloor\lfloor \frac{m}{k} \rfloor$$

最终柿子为：

$$ans = \sum_d d * f(d) = \sum_d d * \sum_{d|k}\mu(\frac{k}{d})\lfloor \frac{n}{k} \rfloor\lfloor \frac{m}{k} \rfloor$$

上面的柿子已经可以做了。它和下面的柿子等价：

$$ans = \sum_k \lfloor \frac{n}{k} \rfloor\lfloor \frac{m}{k} \rfloor \sum_{d|k} d*\mu(\frac{k}{d})$$

---

后记

然而，你发现$\varphi = \mu \times n$。也就是说……上面的柿子等价于：

$$\sum_d \varphi(d) \lfloor \frac{n}{d} \rfloor\lfloor \frac{m}{d} \rfloor$$

一脸辛酸.jpg