[Python] nln(n) time complexity. Count, sort and enumerate
First count nums and sort, we mark largerst value + 1 as n, use presum to calculate how many numbers are less or equeal to v in array precnt. Then we iterate al
First count nums and sort, we mark largerst value + 1 as n, use presum to calculate how many numbers are less or equeal to v in array *precnt*. Then we iterate all *k, v* pair in *cnt*,  *v  (precnt[min((t + 1)  k - 1, n - 1)] - precnt[t  k - 1])  t* will contribute to answer. For example nums = [2,3,4,5,6,7,8],  k = 2, v = 1, when t = 3, we will have ans += v * t * 2, where 2 is the size of [6, 7].  In worst case, time cost is (n / 1 + n /2 + .. . + n / n) = n * (1 /1 + 1 / 2 + ... + 1/n)=nln(n).\n```\nfrom collections import Counter\n\nclass Solution:\n    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n        cnt = sorted(Counter(nums).items())\n        n = cnt[-1][0] + 1\n        precnt, idx = [0] * n, 0\n        for k in range(1, n):\n            precnt[k] = precnt[k - 1]\n            if cnt[idx][0] == k:\n                precnt[k] += cnt[idx][1]\n                idx += 1\n        ans, MOD = 0, 10 ** 9 + 7\n        for k, v in cnt:\n            t = 1\n            while t <= n // k:\n                ans += v * (precnt[min((t + 1) * k - 1, n - 1)] - precnt[t * k - 1]) * t\n                t += 1\n            ans %= MOD\n        return ans\n```
[]