3 Solutions Python
Harmonic Series: 1/1 + 1/2 + 1/3 +  .... + 1/n is logarithmic https://en.wikipedia.org/wiki/Harmonic_series_(mathematics)\nThis fact is used in deriving time co
Harmonic Series: `1/1 + 1/2 + 1/3 +  .... + 1/n` is logarithmic https://en.wikipedia.org/wiki/Harmonic_series_(mathematics)\nThis fact is used in deriving time complexities\n\n**Binary Search Approach\nTime: O(n * logn * logn)\nSpace: O(n)**\n```\ndef sumOfFlooredPairs(self, nums: List[int]) -> int:\n    mx = max(nums)\n    nums.sort()\n    count = Counter(nums)\n    res = 0\n    for i in count:\n        for factor in range(1, mx//i + 1):\n            res += count[i]*factor*(bisect_right(nums, (factor+1)*i - 1) - bisect_left(nums, factor*i))\n    \n    return res % (10**9 + 7)\n```\n\n**Prefix Sum Approach** - get rid of extra logarithmic factor\n**Time: O(n * log n)\nSpace: O(n)**\n```\ndef sumOfFlooredPairs(self, nums: List[int]) -> int:\n    mx = max(nums)\n    count = Counter(nums)\n    prefix = list(accumulate([count[i] if i in count else 0 for i in range(mx + 1)]))\n    res = 0\n    for i in count:\n        for factor in range(1, mx//i + 1):\n            res += factor*count[i]*(prefix[min(i*(factor+1) - 1, mx)] - prefix[i*factor - 1])\n    \n    return res % (10**9 + 7)\n```\n\nSimilar to **Sieve Eratosthenes** Approach\n**Time: O(n * logn)\nSpace: O(n)**\n```\ndef sumOfFlooredPairs(self, nums: List[int]) -> int:\n    mx = max(nums)\n    factorCount = [0]*(mx + 1)\n\n    for num, count in Counter(nums).items():\n        for multiple in range(num, mx + 1, num):\n            factorCount[multiple] += count\n    \n    quotientSum = list(accumulate(factorCount))\n    return sum(map(lambda num: quotientSum[num], nums))%(10**9 + 7)\n```
['Math', 'Binary Search', 'Prefix Sum']