%20%5Ek%20%20%5C%5C%0A%3D%26%5Csum%7Bd%3D1%7D%5E%7Bn%7D%5Csum%7Bi%3D1%7D%5En%20%5Csum%7Bj%3D1%7D%5Em%5Bd%3D%5Cgcd(i%2Cj)%5D%20d%5Ek%20%5C%5C%0A%3D%26%5Csum%7Bd%3D1%7D%5E%7Bn%7D%5Csum%7Bi%3D1%7D%5En%20%5Csum%7Bj%3D1%7D%5Em%5Csum%7Bd%7Ct%7D%7B%7D%5Cmu(%5Cdfrac%7Bt%7D%7Bd%7D)%5Bt%7Cgcd(i%2Cj)%5D%20d%5Ek%20%5C%5C%0A%3D%26%5Csum%7Bt%3D1%7D%5E%7Bn%7D%5Clfloor%5Cdfrac%7Bn%7D%7Bt%7D%5Crfloor%20%5Clfloor%5Cdfrac%7Bm%7D%7Bt%7D%5Crfloor%20%5Csum%7Bd%7Ct%7D%7B%7D%5Cmu(%5Cdfrac%7Bt%7D%7Bd%7D)d%5Ek%20%5C%5C%0A%0A%5Cend%7Baligned%7D%0A#card=math&code=%5Clarge%0A%5Cbegin%7Baligned%7D%0A%26%5Csum%7Bi%3D1%7D%5En%20%5Csum%7Bj%3D1%7D%5Em%20%5Cgcd%28i%2Cj%29%20%5Ek%20%20%5C%5C%0A%3D%26%5Csum%7Bd%3D1%7D%5E%7Bn%7D%5Csum%7Bi%3D1%7D%5En%20%5Csum%7Bj%3D1%7D%5Em%5Bd%3D%5Cgcd%28i%2Cj%29%5D%20d%5Ek%20%5C%5C%0A%3D%26%5Csum%7Bd%3D1%7D%5E%7Bn%7D%5Csum%7Bi%3D1%7D%5En%20%5Csum%7Bj%3D1%7D%5Em%5Csum%7Bd%7Ct%7D%7B%7D%5Cmu%28%5Cdfrac%7Bt%7D%7Bd%7D%29%5Bt%7Cgcd%28i%2Cj%29%5D%20d%5Ek%20%5C%5C%0A%3D%26%5Csum%7Bt%3D1%7D%5E%7Bn%7D%5Clfloor%5Cdfrac%7Bn%7D%7Bt%7D%5Crfloor%20%5Clfloor%5Cdfrac%7Bm%7D%7Bt%7D%5Crfloor%20%5Csum%7Bd%7Ct%7D%7B%7D%5Cmu%28%5Cdfrac%7Bt%7D%7Bd%7D%29d%5Ek%20%5C%5C%0A%0A%5Cend%7Baligned%7D%0A)
设 
%20%3D%20%5Csum%7Bd%7Cn%7D%20%5Cmu(%5Cdfrac%7Bn%7D%7Bd%7D)d%5Ek#card=math&code=%5Clarge%20g%28n%29%20%3D%20%5Csum%7Bd%7Cn%7D%20%5Cmu%28%5Cdfrac%7Bn%7D%7Bd%7D%29d%5Ek) 即可。
这题卡了 
筛，所以这道题的精髓实际上是在推 
考虑 
的性质，发现只要考虑：
稍加讨论即可。
