题目描述
给定 $n$，求
$$
\sum_{i=1}^{n}\sum_{j=1}^{i}\frac{\text{lcm}(i,j)}{\gcd(i,j)}
$$
数据范围：$1 \le n \le 10^9$
题解
首先有几个基本公式：
$$
\begin{cases}
\sum_{i=1}^{n}i=\frac{(1+n)n}{2} \\
\sum_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}{6} \\
\sum_{i=1}^{n}i^3=\left(\frac{(1+n)n}{2}\right)^2 \\
\sum_{d \mid n}\phi(d)=n \\
\sum_{i=1}^{n}[\gcd(i,d)=1]i=\frac{\phi(n)n+[n=1]}{2}
\end{cases}
$$
然后还需要计算一下这个：
$$
\begin{aligned}
&\sum_{i=1}^{n}\frac{\text{lcm}(i,n)}{\gcd(i,n)} \\
=&\sum_{i=1}^{n}\frac{in}{\left(\gcd(i,n)\right)^2} \\
=&\sum_{d \mid n}\sum_{i=1}^{n}[\gcd(i,n)=d]\frac{in}{d^2} \\
=&\sum_{d \mid n}\sum_{i=1}^{\frac{n}{d}}[\gcd(i,\frac{n}{d})=1]\frac{idn}{d^2} \\
=&\sum_{d \mid n}\frac{n}{d}\sum_{i=1}^{\frac{n}{d}}[\gcd(i,\frac{n}{d})=1]i \\
=&\sum_{d \mid n}d\sum_{i=1}^{d}[\gcd(i,d)=1]i \\
=&\sum_{d \mid n}\frac{d\left(d\phi(d)+[d=1]\right)}{2} \\
=&\frac{1+\sum_{d \mid n}d^2\phi(d)}{2}
\end{aligned}
$$
于是就可以开心的推式子了
$$
\begin{aligned}
&\sum_{i=1}^{n}\sum_{j=1}^{i}\frac{\text{lcm}(i,j)}{\gcd(i,j)} \\
=&\sum_{i=1}^{n}\frac{1+\sum_{d \mid i}d^2\phi(d)}{2} \\
=&\frac{1}{2}\left(\left(\sum_{i=1}^{n}1\right)+\left(\sum_{i=1}^{n}\sum_{d \mid i}d^2\phi(d)\right)\right) \\
=&\frac{1}{2}\left(n+\left(\sum_{i=1}^{n}\sum_{d \mid i}d^2\phi(d)\right)\right) \\
=&\frac{1}{2}\left(n+\left(\sum_{i=1}^{n}\sum_{d=1}^{\lfloor \frac{n}{i}\rfloor}d^2\phi(d)\right)\right) \\
\end{aligned}
$$
于是只需要解决后面那个奇奇怪怪的式子
设 $f(d)=d^2\phi(d),g(d)=d^2,h= f \times g$，则有：
$$
\begin{aligned}
h
&=f \times g=\sum_{d \mid n}f(d)g(\frac{n}{d}) \\
&=\sum_{d \mid n}d^2\phi(d)\left(\frac{n}{d}\right)^2 \\
&=n^2\sum_{d \mid n}\phi(d) \\
&=n^2n=n^3
\end{aligned}
$$
现在想求 $F(n)=\sum_{i=1}^{n}f(i)$，然而只有 $G,H$ 可以快速求出来
$$
\begin{aligned}
H(n)&=\sum_{i=1}^{n}h(i) \\
&=\sum_{i=1}^{n}\sum_{d \mid i}f(d)g(\frac{i}{d}) \\
&=\sum_{d=1}^{n}g(d)\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}f(i) \\
&=\sum_{d=1}^{n}g(d)F(\lfloor \frac{n}{d} \rfloor)
\end{aligned}
$$
于是可以推出：
$$
g(1)F(n)=H(n)-\sum_{d=2}^{n}g(d)F(\lfloor \frac{n}{d} \rfloor)
$$
化简可得：
$$
F(n)=\left(\sum_{i=1}^{n}i^3\right)-\left(\sum_{d=2}^{n}d^2F(\lfloor \frac{n}{d} \rfloor)\right)
$$
预处理前 $n^{\frac{2}{3}}$ 项的 $F$，之后递归计算就行了
