题解：我们要求的是这个式子： $ \sum\limits_{i = 1}^n {\gcd (n,i)} $ （下面式子中的d都是n的因子）
变形下 $ \sum\limits_{d = 1}^n {d\sum\limits_{i = 1}^n {\left[ {\gcd (n,i) = d} \right]} } $
即$ \sum\limits_{d = 1}^n {d\sum\limits_{i = 1}^{\frac{n}{d}} {\left[ {\gcd (\frac{n}{d},i) = 1} \right]} } $
所以我们要求的就是 $ \sum\limits_{d = 1}^n {d * \varphi \left( {\frac{n}{d}} \right)} $
直接算就好了
原文：http://www.cnblogs.com/enigma-aw/p/6353994.html