LCMSUM - 图1%20%5C%5C%0A%3D%20%26%20%5Csum%7Bi%3D1%7D%5E%7Bn%7D%20%5Cdfrac%7Bi%5Ccdot%20n%20%7D%7B%5Cgcd(i%2Cn)%7D%20%5C%5C%0A%3D%20%26n%5Ccdot%20%5Csum%7Bi%3D1%7D%5E%7Bn%7D%20%5Csum%7Bd%7Cn%7D%5E%7B%7D%20%5Cdfrac%7Bi%7D%7Bd%7D%20%5B%5Cgcd(i%2Cn)%5D%20%3D%20d%5D%20%5C%5C%0A%3D%20%26n%5Ccdot%20%5Csum%7Bi%3D1%7D%5E%7B%5Cfrac%7Bn%7D%7Bd%7D%7D%5Csum%7Bd%7Cn%7D%5E%7B%7D%20i%5Ccdot%20%5B%5Cgcd(i%2C%5Cdfrac%7Bn%7D%7Bd%7D)%3D1%5D%20%5C%5C%20%0A%3D%20%26n%5Ccdot%5Csum%7Bd%7Cn%7D%5E%7B%7D%5Csum%7Bi%3D1%7D%5E%7B%5Cfrac%7Bn%7D%7Bd%7D%7Di%5Ccdot%20%5B%5Cgcd(i%2C%5Cdfrac%7Bn%7D%7Bd%7D)%20%3D1%20%5D%20%5C%5C%20%0A%3D%20%26n(1%20%2B%20%5Csum%7Bd%7Cn%2C%20d%20%5Cneq%201%7D%20%5Cfrac%20%7Bd%20%5Ccdot%20%5Cvarphi(d)%7D2)%20%5C%5C%20%0A%3D%20%26n(%5Cfrac%2012%20%2B%20%5Csum%7Bd%7Cn%7D%20%5Cfrac%20%7Bd%20%5Ccdot%20%5Cvarphi(d)%7D2)%20%5C%5C%20%0A%26%E4%B8%BA%E4%BA%86%E6%96%B9%E4%BE%BF%E7%9A%84%E7%AD%9B%E5%87%BA%20%5C%20d%20%2C%E6%89%80%E4%BB%A5%E8%BF%99%E6%A0%B7%E8%BD%AC%E6%8D%A2%20%5C%5C%0A%3D%20%26%5Cdfrac%7Bn%7D%7B2%7D%20%2B%20n%5Ccdot%20%5Csum%7Bd%7Cn%7D%5E%7B%7D%20(d%5Ccdot%20%5Cvarphi(d))%20%20%5C%5C%20%0A%25%3D%20%26n%5Ccdot%20%5Csum%7Bd%7Cn%7D%5E%7B%7D%5Csum%7Bi%3D1%7D%5E%7B%5Cfrac%7Bn%7D%7Bd%7D%7D%20%5Cdfrac%7B%5Cvarphi(%5Cfrac%7Bn%7D%7Bd%7D)%20%5Ccdot%20%5Cfrac%7Bn%7D%7Bd%7D%7D%7B2%7D%20%5C%5C%0A%25%3D%20%26n%5Ccdot%5Csum%7Bd%7Cn%7D%5E%7B%7Df(d)%0A%5Cend%7Baligned%7D%0A#card=math&code=%5Clarge%0A%5Cbegin%7Baligned%7D%0A%26%5Csum%7Bi%3D1%7D%5E%7Bn%7D%20%5Ctext%7Blcm%7D%28i%2Cn%29%20%5C%5C%0A%3D%20%26%20%5Csum%7Bi%3D1%7D%5E%7Bn%7D%20%5Cdfrac%7Bi%5Ccdot%20n%20%7D%7B%5Cgcd%28i%2Cn%29%7D%20%5C%5C%0A%3D%20%26n%5Ccdot%20%5Csum%7Bi%3D1%7D%5E%7Bn%7D%20%5Csum%7Bd%7Cn%7D%5E%7B%7D%20%5Cdfrac%7Bi%7D%7Bd%7D%20%5B%5Cgcd%28i%2Cn%29%5D%20%3D%20d%5D%20%5C%5C%0A%3D%20%26n%5Ccdot%20%5Csum%7Bi%3D1%7D%5E%7B%5Cfrac%7Bn%7D%7Bd%7D%7D%5Csum%7Bd%7Cn%7D%5E%7B%7D%20i%5Ccdot%20%5B%5Cgcd%28i%2C%5Cdfrac%7Bn%7D%7Bd%7D%29%3D1%5D%20%5C%5C%20%0A%3D%20%26n%5Ccdot%5Csum%7Bd%7Cn%7D%5E%7B%7D%5Csum%7Bi%3D1%7D%5E%7B%5Cfrac%7Bn%7D%7Bd%7D%7Di%5Ccdot%20%5B%5Cgcd%28i%2C%5Cdfrac%7Bn%7D%7Bd%7D%29%20%3D1%20%5D%20%5C%5C%20%0A%3D%20%26n%281%20%2B%20%5Csum%7Bd%7Cn%2C%20d%20%5Cneq%201%7D%20%5Cfrac%20%7Bd%20%5Ccdot%20%5Cvarphi%28d%29%7D2%29%20%5C%5C%20%0A%3D%20%26n%28%5Cfrac%2012%20%2B%20%5Csum%7Bd%7Cn%7D%20%5Cfrac%20%7Bd%20%5Ccdot%20%5Cvarphi%28d%29%7D2%29%20%5C%5C%20%0A%26%E4%B8%BA%E4%BA%86%E6%96%B9%E4%BE%BF%E7%9A%84%E7%AD%9B%E5%87%BA%20%5C%20d%20%2C%E6%89%80%E4%BB%A5%E8%BF%99%E6%A0%B7%E8%BD%AC%E6%8D%A2%20%5C%5C%0A%3D%20%26%5Cdfrac%7Bn%7D%7B2%7D%20%2B%20n%5Ccdot%20%5Csum%7Bd%7Cn%7D%5E%7B%7D%20%28d%5Ccdot%20%5Cvarphi%28d%29%29%20%20%5C%5C%20%0A%25%3D%20%26n%5Ccdot%20%5Csum%7Bd%7Cn%7D%5E%7B%7D%5Csum%7Bi%3D1%7D%5E%7B%5Cfrac%7Bn%7D%7Bd%7D%7D%20%5Cdfrac%7B%5Cvarphi%28%5Cfrac%7Bn%7D%7Bd%7D%29%20%5Ccdot%20%5Cfrac%7Bn%7D%7Bd%7D%7D%7B2%7D%20%5C%5C%0A%25%3D%20%26n%5Ccdot%5Csum_%7Bd%7Cn%7D%5E%7B%7Df%28d%29%0A%5Cend%7Baligned%7D%0A)

    考虑积性函数的性质：
    设
    LCMSUM - 图2%20%3D%20%5Csum%7Bd%7Cn%7D%5E%7B%7D%20(d%20%5Ccdot%20%5Cvarphi(d))#card=math&code=%5Clarge%20g%28n%29%20%3D%20%5Csum%7Bd%7Cn%7D%5E%7B%7D%20%28d%20%5Ccdot%20%5Cvarphi%28d%29%29)

    LCMSUM - 图3%20%3D%0A%5Cleft%5C%7B%0A%5Cbegin%7Baligned%7D%0A%26g(p%5Ek)%3Dg(p%5E%7Bk-1%7D)%20%2B%20p%5E2-p%20%5C%5C%0A%26g(ab)%3Dg(a)%20%5Ccdot%20g(b)%0A%5Cend%7Baligned%7D%0A%5Cright.%5C%5C%0A#card=math&code=g%28n%29%20%3D%0A%5Cleft%5C%7B%0A%5Cbegin%7Baligned%7D%0A%26g%28p%5Ek%29%3Dg%28p%5E%7Bk-1%7D%29%20%2B%20p%5E2-p%20%5C%5C%0A%26g%28ab%29%3Dg%28a%29%20%5Ccdot%20g%28b%29%0A%5Cend%7Baligned%7D%0A%5Cright.%5C%5C%0A)

    然后筛出 g 可以了。