我们要求 \(\sum\limits_{i=1}^n \gcd(i, n)\)，但 \(gcd\) 没啥卵用，所以尝试给这n个正整数分组。对于 \(gcd(i,n)=1\) 的数给他们归到 \(G(1)\) 这个集合里去，当然，这个集合元素的数量为 \(\phi (n)\)。对于 \(gcd(i,n)=2\) 的数归到 \(G(2)\) 这个集合里去。观察 \(G(2)\) 这个集合可以发现，如果把所有元素都除以2，那么他们都会和 \(\frac{n}{2}\) 互素。那么 \(G(2)\) 这个集合的元素数量即为 \(\phi (\frac{n}{2})\)……找到规律，于是，问题就转化为了：\(\sum\limits_{d\mid n}d*\phi (\frac{n}{d})\)。
又因为 \(n\) 和 \(\frac{n}{d}\) 是一一对应的，所以也可以写成 \(\sum\limits_{d\mid n}\frac{n}{d}*\phi (d)\)。
考虑分解欧拉函数 \(\phi (d) = d(1-\frac{1}{p_1})(1-\frac{1}{p_2})…(1-\frac{1}{p_i})\)
\[\begin{split} \sum\limits_{d\mid n}\frac{n}{d}*\phi (d)&=\sum\limits_{d\mid n}\frac{n}{d}*d\prod_\limits{p_i\mid d}\frac{p_i-1}{p_i}\\ &=\sum\limits_{d\mid n}n*\prod_\limits{p_i\mid d}\frac{p_i-1}{p_i}\\ &=n\sum\limits_{d\mid n}\prod_\limits{p_i\mid d}\frac{p_i-1}{p_i}\\ \end{split} \] 标签：phi,frac,gcd,limits,数论,sum,乘性,笔记,mid From： https://www.cnblogs.com/xiaolemc/p/18176111