自己重新推一遍柿子。/fendou
P2568 GCD
求
\[\sum\limits_{p\in prime}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}[\gcd(i,j)=p] \]gcd的套路转换(
\[\sum\limits_{p\in prime}\sum\limits_{i=1}^{\lfloor \frac{n}{p} \rfloor}\sum\limits_{j=1}^{\lfloor \frac{n}{p} \rfloor}[\gcd(i,j)=1] \]然后发现\(\sum[\gcd(i,j)=1]\)这不是欧拉函数吗，但是由于是有序数对，所以可以转换为
\[\sum\limits_{p\in prime}2\times\sum\limits_{i=1}^{\lfloor \frac{n}{p} \rfloor}\phi(i)-1 \]减一是因为\(i=j\) 时会被重复算，最后复杂度 \(\mathcal{O(n)}\)。