LC 1862. 向下取整数对和

https://leetcode-cn.com/problems/sum-of-floored-pairs/

这题很有意思的点在于，floor/ceil这类函数是没有办法通常乘法来做到减少计算的。也就是说 floor(X/Y) = floor(X/Z) * floor(Z/Y). 我之前还考虑过是否要保留X/Y的原始累计值，但是发现这个思路也是错误的。

打开下面两个提示，就会有思路：

Find the frequency (number of occurrences) of all elements in the array. # 这个不算是思路，因为有重复元素，所以频数肯定是要做统计的
For each element, iterate through its multiples and multiply frequencies to find the answer. # 这个提示很有用，可以变为寻找x的乘数。

也就是说，我们要换个思路。如果数组中存在某个X，我们可以去寻找

[X, 2X) 所有数的出现次数A, 那么这些数的floor(arr[i]/X) = 1, 所以总数就是A
[2X,3X) 所有数的出现次数B，那么这些数的floor(arr[i]/X) = 2, 所以总数就是2*B
以此类推，直到超过数组最大数为止。

关于时间复杂度不太好计算，可能最坏的情况就是没有重复的数组[1..10^5]了。这个情况下面需要进行：10^5(1+1/2+1/3+…) 后面部分是个调和级数 https://zh.wikipedia.org/wiki/%E8%B0%83%E5%92%8C%E7%BA%A7%E6%95%B0. 这个值大约是12.09. 所以应该是不会超时的。

In [1]: s = 0

In [2]: for i in range(1, 10**5+1):
   ...:     s += 1/i

In [3]: s
Out[3]: 12.090146129863335

代码如下，计算出现次数的话可以使用前缀和。

class Solution:
    def sumOfFlooredPairs(self, nums: List[int]) -> int:
        N = min(10 ** 5, max(nums))
        occ = [0] * (1 + N)
        for x in nums:
            occ[x] += 1
        acc = [0] * (2 + N)
        for i in range(1, N + 1):
            acc[i + 1] = occ[i]
            acc[i + 1] += acc[i]

        ans = 0
        for x in range(1, 1 + N):
            if occ[x] == 0: continue
            m = 1
            while True:
                t = m * x
                if t > N: break
                s, e = t, min(t + x - 1, N)
                tt = acc[e + 1] - acc[s]
                # if tt:
                #     print(x, m, s, e, tt)
                ans += tt * occ[x] * m
                m += 1

        MOD = 10 ** 9 + 7
        return ans % MOD