[Java] O(n log(n)) Straightforward brute force with explanation, 76 ms
Intuition\n\nThe simplest method that everyone would come up with is to calculate floor(nums[i] / nums[j]) for each pair and add them up.\n\njava\n// Omitted mo
## Intuition\n\nThe simplest method that everyone would come up with is to calculate `floor(nums[i] / nums[j])` for each pair and add them up.\n\n```java\n// Omitted modulo operations\nint m = nums.length;\nint sum = 0;\nfor (int i = 0; i < m; ++i) {\n    for (int j = 0; j < m; ++j) {\n        sum += nums[i] / nums[j];\n    }\n}\n```\n\nHowever, since there\'re at most 10^5 elements in total, such an `O(m^2)` (`m = nums.length, m <= 10^5`) solution would surely get TLE for large inputs. But the idea itself is not bad. In fact, we only need to slightly modify the above naive approach to get it to work.\n\nThe key idea is simple: **consider elements in groups rather than individually**.\n\nObserve that the problem description kindly restricts the value of array elements to the range [1, 10^5]. Hence the quotient of any pair of elements can never exceed 10^5 as well.\n\nWe want to sum the floored quotients of paired elements. For any integer `x` between `k * a <= x < (k + 1) * a` where `a` and `k` are positive intergers, `floor(x / a) = k` holds. Thus given the divisor `a`, what really matters is **to which interval** an integer `x` belongs.\n\nFor an integer `a`, the following intervals `[0, a), [a, 2a), [2a, 3a), ...` correspond to floored quotients `0, 1, 2, ...` respectively. Since the dividend, divisor and quotient all fall into [1, 10^5], the number of intervals is bounded by `10^5 / a`. There can be multiple `a`\'s, but they should be identical for our purpose and can be simply counted together.\n\nTherefore, we can use counting sort to store the count of each value in the original array. Then we consider each value one by one as a *divisor*. Now we only need to compute how many elements fall into the intervals above separately. If there\'re `m` elements that fall into `[k * a, (k + 1) * a)`, we add `m * k` to our result.\n\nThe only problem left is *how to count the numbers in an interval efficiently*. Again notice that all values fall into [1, 10^5] and we already count them using counting sort. As in the output phase in counting sort, let `counts[i] += counts[i - 1]` for each value from `i = 1 to 10^5`. In this way, `counts` array stores the number of elements `j` such that `j <= i`, and thus the number of elements that fall into `[a, b)` can be represented by `counts[b - 1] - counts[a - 1]`.\n\n## Running time analysis\n\nFor each divisor `a` between `1 <= a <= n`, we consider `n/a` intervals, and we can retrieve the number of elements falling into specific interval in `O(1)` time. Therefore the running time is\n\n```\nT(n) <= n/1 + n/2 + n/3 + ... + n/n\n    = n * (1/1 + 1/2 + 1/3 + ... + 1/n)\n    < n * (ln(n) + 1) (by 1/x < ln(x) - ln(x-1) for all x > 1)\n```\n\nSo the time complexity is `O(n log(n))`.\n\n*Note*: To be precise, we must perform a linear scan to count the elements in the array, which takes linear `O(m)` time (`m = nums.length`). Thus `O(m + n log(n))` would be a more accurate expression.\n\n## Implementation\n*Note*: (credited to @yubad2000) the constant declaration of `MAX` can be further replaced by the actual maximum value in the array through a linear scan, which could bound the running time more tightly.\n\n```java\nclass Solution {\n    static final int MAX = (int)1e5;\n    static final int MODULUS = (int)1e9 + 7;\n    \n    public int sumOfFlooredPairs(int[] nums) {\n        int[] counts = new int[MAX + 1];\n        for (int num : nums) {\n            ++counts[num];\n        }\n        for (int i = 1; i <= MAX; ++i) {\n            counts[i] += counts[i - 1];\n        }\n        \n        long total = 0;\n        for (int i = 1; i <= MAX; ++i) {\n            if (counts[i] > counts[i - 1]) {\n                long sum = 0;\n                // [i * j, i * (j + 1)) would derive a quotient of j\n                for (int j = 1; i * j <= MAX; ++j) {\n                    int lower = i * j - 1;\n                    int upper = i * (j + 1) - 1;\n                    sum += (counts[Math.min(upper, MAX)] - counts[lower]) * (long)j;\n                }\n                total = (total + (sum % MODULUS) * (counts[i] - counts[i - 1])) % MODULUS;\n            }\n        }\n        return (int)total;\n    }\n}\n```\n\n---\n\n*Update1*: fix the skip logic in code\n*Update2*: add further improvements and supplements to running time analysis\n*Update3*: correct and refine running time analysis
[]