第二个\( O(T\sqrt(n)) \)复杂度T了..T了..T了...天地良心，这能差多少？！
于是跑去现算（。
\[
\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}gcd(i,j)
\]
\[
\sum_{d=1}^{n}d\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}[gcd(i,j)==d]
\]
\[
\sum_{d=1}^{n}d(\sum_{j=1}^{n}\sum_{i=1}^{j}[gcd(i,j)==d]-\sum_{j=1}^{n}[gcd(j,j)==d])
\]
\[
\sum_{d=1}^{n}d(\sum_{j=1}^{\left \lfloor \frac{n}{d} \right \rfloor}\sum_{i=1}^{j}[gcd(i,j)==1]-1)
\]
\[
\sum_{d=1}^{n}d(\sum_{j=1}^{\left \lfloor \frac{n}{d} \right \rfloor}\phi(j)-1)
\]
然后与\( O(nlnn) \)处理出所有答案。
#include
京公网安备 11010802041100号