莫比乌斯反演入门。

    P2522 [HAOI2011]Problem b - 图1%20%3D%3D%20k%5D%20%5C%5C%0A%3D%26%5Csum%7Bi%3D1%7D%5E%7B%5Cfrac%7Bn%7D%7Bk%7D%7D%5Csum%7Bj%3D1%7D%5E%7B%5Cfrac%7Bm%7D%7Bk%7D%7D%20%5Cepsilon(%5Cgcd(i%2Cj))%20%5C%5C%20%0A%5Cend%7Baligned%7D%0A#card=math&code=%5Cbegin%7Baligned%7D%0A%26%E6%B1%82%3A%5C%5C%0A%26%5Csum%7Bi%3D1%7D%5E%7Bn%7D%5Csum%7Bj%3D1%7D%5E%7Bm%7D%5B%5Cgcd%28i%2Cj%29%20%3D%3D%20k%5D%20%5C%5C%0A%3D%26%5Csum%7Bi%3D1%7D%5E%7B%5Cfrac%7Bn%7D%7Bk%7D%7D%5Csum%7Bj%3D1%7D%5E%7B%5Cfrac%7Bm%7D%7Bk%7D%7D%20%5Cepsilon%28%5Cgcd%28i%2Cj%29%29%20%5C%5C%20%0A%5Cend%7Baligned%7D%0A)

    考虑到 P2522 [HAOI2011]Problem b - 图2

    也就是:

    P2522 [HAOI2011]Problem b - 图3%7D%5E%7B%7D%20%5Cmu(d)%0A%5Cend%7Baligned%7D%0A#card=math&code=%5Cbegin%7Baligned%7D%0A%5Csum%7Bi%3D1%7D%5E%7B%5Cfrac%7Bn%7D%7Bc%7D%7D%5Csum%7Bj%3D1%7D%5E%7B%5Cfrac%7Bm%7D%7Bk%7D%7D%5Csum_%7Bd%7C%5Cgcd%28i%2Cj%29%7D%5E%7B%7D%20%5Cmu%28d%29%0A%5Cend%7Baligned%7D%0A)

    image.png
    当 i=x,j=y 时可以容斥解决。