https://www.51nod.com/Challenge/Problem.html#!#problemId=1188
求\(\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n}gcd(i,j)\)
首先交换求和\(\sum\limits_{j=2}^{n}\sum\limits_{i=1}^{j-1}gcd(i,j)=\sum\limits_{j=2}^{n}\sum\limits_{i=1}^{j}gcd(i,j)-j\)
像之前那样用莫比乌斯反演搞出
\(\sum\limits_{g=1}^{n}g\sum\limits_{i=1}^{\lfloor\frac{n}{g}\rfloor}{\varphi(i)}, (\varphi(1)=0)\)
或者
\(\sum\limits_{g=1}^{n}g\sum\limits_{i=1}^{\lfloor\frac{n}{g}\rfloor}{\mu(i)}*{\lfloor\frac{n}{i*g}\rfloor}^2\)
都是T了，说明单次回答的复杂度非常感人，原因是因为跟n有关就逃不了分块。
所以分块的复杂度还是太高了。
然后惊人的事情发生了。
这道题和前面的不一样的地方在于，他的n其实没有前面的大，只是多！
分块的意义在于加快单次回答的速度，所以才把g提了出来分块，现在不太合适。
正解，先求解：
\(\sum\limits_{i=1}^{n}gcd(i,n)\)
这个东西可以枚举g：
\(\sum\limits_{g=1}^{n}g\sum\limits_{i=1}^{n}[gcd(i,n)==g]\)
\(\sum\limits_{g=1}^{n}g\sum\limits_{i=1}^{\lfloor\frac{n}{g}\rfloor}[gcd(i,\lfloor\frac{n}{g}\rfloor)==1]\)
\(\sum\limits_{g=1}^{n}g\varphi(\lfloor\frac{n}{g}\rfloor)\)
这个有什么不对呢？其实没什么不对，就是不好。因为gcd必定是整除n的，所以可以：
\(\sum\limits_{g|n}g\varphi(\lfloor\frac{n}{g}\rfloor)\)
这明显就是一个积性函数，记为 \(p(n)\) ，处理好就可以了。原式：
\(\sum\limits_{j=2}^{n}p(j)-j\)
其他尝试？
现在把g放回去。
\(\sum\limits_{g=1}^{n}\sum\limits_{i=1}^{\lfloor\frac{n}{g}\rfloor}g*{\varphi(i)}, (\varphi(1)=0)\)
这个不就是相当于把每个 \(i*g \leq n\) 的加起来吗？所以当然可以交换求和顺序！
\(\sum\limits_{i=1}^{n}\sum\limits_{g=1}^{\lfloor\frac{n}{i}\rfloor}g*{\varphi(i)}, (\varphi(1)=0)\)
前面是一个干净的前缀和，后面那个式子是nlogn的！
也就是预处理：
\(ans(n)=\sum\limits_{g=1}^{\lfloor\frac{n}{i}\rfloor}g*{\varphi(i)}, (\varphi(1)=0)\)
51nod - 1188 - 最大公约数之和 V2 - 数论
原文：https://www.cnblogs.com/Yinku/p/10987435.html