title
给你一个整数数组 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
solution
前缀和。
class Solution:
def sumOfFlooredPairs(self, nums: List[int]) -> int:
if not nums: return 0
mod = 10 ** 9 + 7
ans = 0
nums = sorted(nums)
upper = nums[-1]
pre = [0] * (upper + 1)
counter = collections.Counter(nums)
for i in range(nums[0], nums[-1] + 1, 1):
pre[i] = pre[i - 1] + counter[i]
# 前缀和
def sumv(a, b):
return pre[b] - pre[a]
for v in range(1, upper + 1):
if counter[v]:
k = 1
while k * v <= upper:
ans += sumv(k * v - 1, min(upper, k * v + v - 1)) * k * counter[v]
ans %= mod
k += 1
return ans