题意:

设:

f_2(n)=\sum_{i=1}^n \sum_{j=i}^n [lcm(i,j)=n]\\ g_2(n)=\sum_{i=1}^nf_2(i)\\

g_2(10^{12})

sol

f(n)=\sum_{i=1}^n \sum_{j=1}^n [lcm(i,j)=n]\\ g(n)=\sum_{i=1}^n f(n)\\

so… f_2(n)=\frac{f(n)+1}{2}

同理于 g_2(n)=\frac{g(n)+n}{2}

引理

\begin{aligned} f(n) &=\sum_{i=1}^n \sum_{j=1}^n[lcm(i,j)=n]\\ &=\sum_{i|n} \sum_{j|n} [\gcd(i,j)=1] \end{aligned}

Proof:

考虑lcm(i,j)=n除去两者的\gcd.

i, j剩下的质因子是不交的, 且并集还是n的因子

故, 上式是满足的.

进一步转换题目

\begin{aligned} &{=\sum_{i j | n}[\operatorname{gcd}(i, j)=1]} \\ &{=\sum_{i j | n} \sum_{d|i, d| j} \mu(d)} \end{aligned}

\begin{aligned} g(n) &=\sum_{k=1}^{n} f(k) \\ &=\sum_{d=1}^{n} \mu(d) \sum_{d | i} \sum_{d | j} \lfloor \frac{n}{i j} \rfloor \\ &=\sum_{d=1}^{n} \mu(d) \sum_{i, j}\left\lfloor\frac{n}{d^{2} i j}\right\rfloor \\ &=\sum_{d=1}^{n} \mu(d) \sum_{x}\left\lfloor\frac{n}{d^{2} x}\right\rfloor \sigma_{0}(x) \\ &=\sum_{d=1}^{\sqrt{n}} \mu(d) S\left(\left\lfloor\frac{n}{d^{2}}\right\rfloor\right) \end{aligned}

可以利用: \sigma_{0} * \mu=1 * 1 * \mu=1

或者直接求: \sum_{i=1}^{n} \sigma_{0}(i)=\sum_{i=1}^{n}\left\lfloor\frac{n}{i}\right\rfloor