求 S(n) = ∑_i∈[1,n]∑_j∈[1,n] F(i,j),n<=10⁹

    F(i,j) = ∑_d∈[1,i*j] [d | i*j]

1. 化简S(n)

step 1.

    F(i,j) = ∑_d∈[1,i*j] [d/gcd(i,d) | i*j/gcd(i,d)]

             = ∑_d∈[1,i*j] [d/gcd(i,d) | j]

step 2.

    S(n) = ∑_i∈[1,n]∑_j∈[1,n]∑_d∈[1,i*j] [d/gcd(i,d) | j]

           = ∑_i∈[1,n]∑_d∈[1,i*n] [n/(d/gcd(i,d)]

           = ∑_i∈[1,n]∑_d∈[1,i*n] [n*gcd(i,d)/d]

step 3.

    S(n) = ∑_i∈[1,n]∑_d∈[1,i*n]∑_k [gcd(i,d)==k]*[n*k/d]

           = ∑_k∑_i∈[1,n/k]∑_d∈[1,n] [gcd(i,d)==1]*[n/d]

    S(n) = ∑_i∈[1,n]∑_d∈[1,n]∑_k∈[1,n/i] [gcd(i,d)==1]*[n/d]

            = ∑_i∈[1,n]∑_d∈[1,n] [gcd(i,d)==1]*[n/d]*[n/i]

    S(n) = ∑_i∈[1,n]∑_j∈[1,n] [gcd(i,j)==1]*[n/i]*[n/j]

step 4.

    S(n) = ∑_d μ(d)*∑_i∈[1,n/d] ∑_j∈[1,n/d] [n/(id)]*[n/(jd)]

           = ∑_d μ(d)*∑_i∈[1,n/d] [n/(id)]*∑_j∈[1,n/d] [n/(jd)]

    令g(n) = ∑_i∈[1,n] [n/i],则S(n) = ∑_d μ(d)*g([n/d])²

    只计算所有不同的[n/d],可以做到O(n^2/3)

2.0 计算M(n) = ∑_i∈[1,n] μ(i)

    M(n) = ∑_i∈[1,n] μ(i)

            = ∑_i∈[1,n] (∑_d|i μ(d) - ∑_d|i,d<i μ(d))

            = 1 - ∑_i∈[1,n]∑_d|i,d<i μ(d)

            = 1 - ∑_d|i,d<i∑_i∈[1,n] μ(d)

            = 1 - ∑_d∈[1,n] ∑_i∈[2,n/d] μ(d)

            = 1 - ∑_i∈[2,n] ∑_d∈[1,n/i] μ(d)

            = 1 - ∑_i∈[2,n] M([n/i])

    筛出n^2/3以内的M，查询的时候查表O(1)回答.

    对于大于n^2/3的情况，我们用hash表来记忆化.

    这样能做到O(n^2/3)的复杂度.

2.1 计算F(n) = ∑_i∈[1,n] phi(i)

     由n = ∑_d|n phi(d) ,我们可以类似地得到F(n)的计算方法

     F(n) = ∑_i∈[1,n] phi(i)

            = ∑_i∈[1,n] (∑_d|i phi(d) - ∑_d|i,d<i phi(d))

            = n(n+1)/2 - ∑_i∈[1,n]∑_d|i,d<i phi(d)

            = n(n+1)/2 - ∑_i∈[2,n] F([n/i])

3. 码码码