日记

Wed Jul 02 2025

3 label.readTime

445 label.wordCount

今天终于知道了什么是真正的性能。

我们直接开始推柿子：

\begin{aligned} ans & = \sum_{i = 1}^{n}\sum_{j = 1}^{n}\gcd(i,j) \\ & = \sum_{d = 1}^{n}d\sum_{i = 1}^{n}\sum_{j = 1}^{n}[\gcd(i,j) = d] \\ & = \sum_{d = 1}^{n}d\sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j = 1}^{\lfloor \frac{n}{d} \rfloor}[\gcd(i,j) = 1] \\ & = \sum_{d = 1}^{n}d\sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j = 1}^{\lfloor \frac{n}{d} \rfloor}\sum_{g \mid \gcd(i,j)}\mu(g) \\ & = \sum_{d = 1}^{n}d\sum_{g = 1}^{\lfloor \frac{n}{d} \rfloor}\mu(g)\sum_{i = 1}^{\lfloor \frac{n}{gd} \rfloor}\sum_{j = 1}^{\lfloor \frac{n}{gd} \rfloor}1 \\ & = \sum_{d = 1}^{n}d\sum_{g = 1}^{\lfloor \frac{n}{d} \rfloor}\mu(g) \cdot \lfloor \frac{n}{gd} \rfloor^2 \end{aligned}

我们枚举 $T = gd$ ：

\begin{aligned} ans & = \sum_{d = 1}^{n}d\sum_{g = 1}^{\lfloor \frac{n}{d} \rfloor}\mu(g) \cdot \lfloor \frac{n}{gd} \rfloor^2 \\ & = \sum_{T = 1}^{n}\lfloor \frac{n}{T} \rfloor^2 \sum_{d \mid T}d \cdot \mu(\frac{T}{d}) \end{aligned}

我们发现 $\sum_{d \mid T}d \cdot \mu(\frac{T}{d}) = (\operatorname{Id} * \mu)(T) = \varphi(T)$ ， $*$ 表示狄利克雷卷积。于是原式变成这样：

ans = \sum_{T = 1}^{n}\lfloor \frac{n}{T} \rfloor^2 \cdot \varphi(T)

可以用数论分块，用杜教筛求解 $\varphi$ 的前缀和。时间复杂度 $O(\text{能过})$ 。

这个 20s 时限是认真的吗？

我们继续推式子：

\begin{aligned} ans & = \sum_{i = 1}^{n}\sum_{j = i + 1}^{n}\gcd(i,j) \\ & = \sum_{i = 1}^{n}\sum_{j = 1}^{i - 1}\gcd(i,j) \\ & = \sum_{d = 1}^{n}d\sum_{i = 1}^{n}\sum_{j = 1}^{i - 1}[\gcd(i,j) = d] \\ & = \sum_{d = 1}^{n}d\sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j = 1}^{i - 1}[\gcd(i,j) = 1] \\ & = \sum_{d = 1}^{n}d\sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor}\varphi(i) \end{aligned}

然后就是愉快的杜教筛 + 数论分块。

然后看这个 20s 时限，想着自己造一组数据，于是就有了这个

今天晚上全取改杜教筛了，全然没有注意有一车人已经把综合训练改了。

但是该说不说这个综合训练是真的唐。~~我也是真的唐~~