难度: Hard
给你一个整数数组 nums ，请你返回所有下标对 0 <= i, j < nums.length 的 floor(nums[i] / nums[j]) 结果之和。由于答案可能会很大，请你返回答案对109 + 7 取余 的结果。
函数 floor() 返回输入数字的整数部分。
示例 1：
输入：nums = [2,5,9] 输出：10 解释： floor(2 / 5) = floor(2 / 9) = floor(5 / 9) = 0 floor(2 / 2) = floor(5 / 5) = floor(9 / 9) = 1 floor(5 / 2) = 2 floor(9 / 2) = 4 floor(9 / 5) = 1 我们计算每一个数对商向下取整的结果并求和得到 10 。
示例 2：
输入：nums = [7,7,7,7,7,7,7] 输出：49
提示：
1 <= nums.length <= 1051 <= nums[i] <= 105运行时间: 568 ms
内存: 35.7 MB
class Solution:
def sumOfFlooredPairs(self, nums: List[int]) -> int:
c = Counter(nums)
store = [0] * (1 + max(nums))
for x in c:
for y in range(x, len(store), x):
store[y] += c[x]
store = list(accumulate(store))
return sum(store[x] for x in nums) % (10**9+7)
这个题解采用了哈希表和前缀和的方法来高效地计算所有数对的向下取整和。首先，使用Counter来计数数组中每个数字出现的次数。接着，创建一个数组store，其长度为数组中最大数加一。对于每一个在nums中出现的数x，更新store数组，将x的倍数的位置增加x出现的次数。这样做是因为，任意数y被x整除的商就是y/x。之后，计算store的前缀和，这样每个store[y]就包含了所有小于等于y的数除以其它数的商的和。最后，通过遍历nums数组，累加这些前缀和得到最终结果，并取模10^9+7返回。
时间复杂度: O(n + m log m)
空间复杂度: O(m)
class Solution:
def sumOfFlooredPairs(self, nums: List[int]) -> int:
c = Counter(nums) # 计数每个数字出现的次数
store = [0] * (1 + max(nums)) # 初始化store数组
for x in c: # 遍历每个数字
for y in range(x, len(store), x): # 更新x的所有倍数的位置
store[y] += c[x]
store = list(accumulate(store)) # 计算前缀和
return sum(store[x] for x in nums) % (10**9+7) # 对所有nums中的数，累加其前缀和并取模
使用哈希表（Counter）来计数是因为这种方法可以快速统计每个数字的出现次数，并且可以直接访问每个唯一值及其频率。如果直接在遍历时计算，则每次更新操作可能需要遍历整个数组来查找相同的值，这将使时间复杂度增加。哈希表优化了这一过程，使得时间复杂度降低，并且代码实现更简洁高效。
在store数组中，每个索引位置y代表的是所有小于等于y的数字除以其他数字的商的和。对于一个特定的数字x，它能整除的数字包括x, 2x, 3x等。因此，对于nums中每一个出现的x，我们需要在store数组中x的所有倍数的位置上累加x出现的次数。这样做是为了在计算前缀和时，能够通过store[y]快速得到所有合法的商的累加值，这些商是由所有小于等于y的数字除以x得到的。
计算store数组的前缀和后，每个位置y的值将包含所有小于等于y的索引处的值的总和。这意味着store[y]实际上包含了所有小于等于y的数除以所有可能的数x（x是数组nums中的元素）的商的和。通过前缀和，我们可以在O(1)的时间内直接获取到任何y值对应的累计商的和，这极大地优化了查询效率。
对结果取模10^9+7是一个常见的技巧，主要用于防止在处理非常大的整数时发生溢出，并且可以保持最终结果的大小在一个合理的范围内。10^9+7是一个大的质数，常用于编程竞赛和算法实现中，因为它可以减少在模运算中的冲突，并且配合使用快速幂等算法，可以高效地处理大数的问题。