设
\[
f(n)=\sum_{d \vert n}(d,\frac{n}{d})\F(n)= \sum_{i=1}^n{f(i)}
\]
求\(F(n)，n\leq 10^{15}, Q=1\)
sol：
无法直接转化\(f(n)\)，尝试暴力展开\(f(i)\)后直接莫比乌斯反演转化\(F(n )\)：
\[
\begin{aligned}
F(n) &= \sum_{i=1}^n\sum_{d\vert n}(d,\frac{n}{d})\&=\sum_d{d\sum_{i=1}^n{\sum_{e\vert i}{[(e,\frac{i}{e})=d]}}}\&=\sum_{d}d\sum_{i=1}^{n/d^2}\sum_{e\vert i}[(e,\frac{i}{e})=1]\&=\sum_{d}d\sum_{i=1}^{n/d^2}\sum_{e\vert i}\sum_{j\vert e}\sum_{j\vert(i/e)}\mu(e)\&=\sum_{d}\sum_{j=1}^{n/d^2}d\space \mu(j)\sum_{i=1}^{n/d^2}\sum_{e\vert i}[j\vert e][j\vert \frac{i}{e}]\&=\sum_{d}\sum_{j=1}^{n/d^2}d\space\mu(j)\sum_{i=1}^{n/d^2j^2}\sigma_0(i)
\end{aligned}
\]
发现其实将\(j\)的上界扩展到\(n\)不会产生任何影响
\[
F(n)=\sum_{d}\sum_{j=1}^{n}d\space \mu(j)\sum_{i=1}^{n/d^2j^2}\sigma_0(i)
\]
考虑枚举\(T=dj\)，设\(S(n)=\sum_{i=1}^n\sigma_0(i)\)，发现\(id\)和\(\mu\)构成卷积。
\[
F(n)=\sum_{T=dj=1}^n\phi(T)S(\lfloor\frac{n}{T^2} \rfloor)
\]
当\(d>\sqrt n\)\(\frac{n}{T^2}\)恒为0，因此缩小枚举\(T\)的上界为\(\sqrt n\)，同时\(S(n)\)可以分块优化。
\[
F(n)=\sum_{T=dj=1}^{\sqrt n}\phi(T)S(\lfloor\frac{n}{T ^2} \rfloor)
\]
复杂度\(\sqrt n \ln \sqrt n\) 反正是提答
[Project Euler 530] GCD of Divisors
原文：https://www.cnblogs.com/cjc030205/p/11638104.html