求 ∑_n∈[1,N]∑_m∈[1,M]∑_k∈[0,m) [(nk+x)/m] (N,M<=500000,x为实数且x∈[0,100000])

0.首先令x = [x]显然是不影响结果的

1.先考虑如何化简∑_k∈[0,m) [(nk+x)/m]

     首先显然有：[(nk+x)/m] = [(nk%m+x)/m]+[nk/m]

                         [(nk+x)/m] = [(nk%m+x)/m]+(nk-nk%m)/m

    则∑_k∈[0,m) [(nk+x)/m] = ∑_k∈[0,m) [(nk%m+x)/m] + ∑_k∈[0,m) nk/m + ∑_k∈[0,m) nk%m/m

    令d=gcd(n,m)，则∑_k∈[0,m) [(nk%m+x)/m] = d([x/m]+[(x+d)/m]+...+[(x+m-d)/m])

                                                                  = d([(x/d)/(m/d)]+[((x/d)+1)/(m/d)]+...+[((x/d)+m/d-1)/(m/d)])

                                                                  = d([(x/d)(m/d)/(m/d)] (注)

                                                                  = d[x/d]

      ∑_k∈[0,m) nk%m = d(0+d+...+m-d)

                            = (m-d)/2

      ∑_k∈[0,m) [(nk+x)/m] = d[x/d]+n(m-1)/2+(d-m)/2

                                   = d[x/d]+(n-1)(m-1)/2+(d-1)/2

     由此可见：∑_k∈[0,m) [(nk+x)/m] = ∑_k∈[0,n) [(mk+x)/n]

注：

     对于正整数m和实数x, [mx] = [x] + [x + 1/m] + ... + [x + (m-1)/m]

     证明：

                x = [x] + {x}

                设：k = [m{x}]

                则k/m <= m{x} < (k+1)/m

                [mx] = [m([x] + {x})]

                        = m[x] + [m{x}]

                        = m[x] + k                   

                [x]+[x+1/m]+...+[x+(m-1)/m]

             = m[x] + [{x}+1/m] + ... + [{x}+(m-1)/m]

             = m[x] + k

                [mx] = [x] + [x + 1/m] + ... + [x + (m-1)/m]

2. 再考虑如何计算∑_n∈[1,N]∑_m∈[1,M] d[x/d]+(n-1)(m-1)/2+(d-1)/2 (d=gcd(n,m))

     分为3部分计算：

            1)  ∑_n∈[1,N]∑_m∈[1,M]  d[x/d]

            2) ∑_n∈[1,N]∑_m∈[1,M]  (n-1)(m-1)/2

            3) ∑_n∈[1,N]∑_m∈[1,M]  (d-1)/2

      1) 和 3) 考虑容斥，枚举d , 再枚举d的倍数，复杂度O(nlogn)

      2) 可以直接O(1)计算

3.码码码