题解:我们要求的是这个式子: $ sumlimits_{i = 1}^n {gcd (n,i)} $ (下面式子中的d都是n的因子)
变形下 $ sumlimits_{d = 1}^n {dsumlimits_{i = 1}^n {left[ {gcd (n,i) = d} ight]} } $
即$ sumlimits_{d = 1}^n {dsumlimits_{i = 1}^{frac{n}{d}} {left[ {gcd (frac{n}{d},i) = 1} ight]} } $
所以我们要求的就是 $ sumlimits_{d = 1}^n {d * varphi left( {frac{n}{d}}
ight)} $
直接算就好了