Prefix Sum, Fenwick Tree, Sort and Sieve
Let max_n be the maximum number in our array. For each number n, we consider all possible factors f in [1, max_n / n].\n\nWe start from the largest factor, and 
Let `max_n` be the maximum number in our array. For each number `n`, we consider all possible factors `f` in `[1, max_n / n]`.\n\nWe start from the largest factor, and count how many numbers in our array are greater or equal than `f * n`. Then, we multiply this count by `f` and add it to our result.  We then count elements greater or equal than `(f - 1) * n`, but smaller than `f * n`. And so on.\n\nTo count elements in efficiently, we can use a prefix sum array. However, population of that array requires a quadratic time.  We have a few options here:\n\n- Use a line sweep approach to compute the prefix sum in linear time.\n- Use a Fenwick Tree, that can do the same in the logarithmic time.\n- Alternativelly, we can sort our array and binary-search for `f * n`. See solution 3.\n\n> There is a different way to look at this, proposed by [Ceay](https://leetcode.com/problems/sum-of-floored-pairs/discuss/1210057/Python-Five-lines-O(-n-log-n)). His solution reminds me Sieve of Eratosthenes, where we add the count of `n` to `[n, 2 * n, 3 * n...]` elements in our sieve. I provided a C++ version of his solution below.\n\n#### Solution 1: Prefix Sum + Line Sweep\nThe code can be simplified if we do not have to deal with duplicates (e.g. `[1, 1, 1, .... 1, 100000]` test case, which is missing from OJ).\n\n**C++ (188 ms)**\n```cpp\nint ps[100001] = {};\nint sumOfFlooredPairs(vector<int>& nums) {\n    long res = 0, max_n = *max_element(begin(nums), end(nums));\n    for (auto n : nums)\n        ++ps[n];\n    vector<pair<int, int>> n_cnt;\n    for (auto i = 1; i <= max_n; ++i) {\n        if (ps[i])\n            n_cnt.push_back({i, ps[i]});\n        ps[i] += ps[i - 1];\n    }\n    for (auto &[n, cnt] : n_cnt)\n        for (long f = max_n / n; f > 0; --f)\n            res = (res + cnt * f * (ps[min(max_n, (f + 1) * n - 1)] - ps[f * n - 1])) % 1000000007;\n    return res;\n}\n```\n#### Solution 2: Fenwick Tree\nWe do not have to use `m` for this solution to get accepted, but it would fail for `[1, 1, 1, .... 1, 100000]` test case.\n\n**C++ (456 ms)**\n```cpp\nint bt[100002] = {};\nint bitSum(int i)\n{\n    int sum = 0;\n    for (i = i + 1; i > 0; i -= i & (-i))\n        sum += bt[i];\n    return sum;\n}\nvoid bitUpdate(int n, int i, int val)\n{\n    for (i = i + 1; i <= n; i += i & (-i))\n        bt[i] += val;\n}    \nint sumOfFlooredPairs(vector<int>& nums) {\n    long res = 0, max_n = *max_element(begin(nums), end(nums));\n    unordered_map<int, int> m;\n    for (auto n : nums) {\n        ++m[n];\n        bitUpdate(max_n + 1, n, 1);\n    }\n    for (auto [n, cnt] : m)\n        for (long f = max_n / n; f > 0; --f)\n            res = (res + cnt * f * ((bitSum(min(max_n, (f + 1) * n - 1)) - bitSum(f * n - 1)))) % 1000000007;\n    return res;\n}\n```\n#### Solution 3: Sort\nSame idea, but we sort the array and binary-search for `f * n`. When we find that element, we can easily tell how many elements are after it. The code below is optimized to deal with test cases with many repeating elements.\n\n**C++ (956 ms)**\n```cpp\nint sumOfFlooredPairs(vector<int>& nums) {\n    sort(begin(nums), end(nums));\n    long res = 0, max_n = nums.back();\n    for (int i = 0, k = 1; i < nums.size(); i += k) {\n        k = 1;\n        while (i + k < nums.size() && nums[i] == nums[i + k])\n            ++k;\n        auto prev = end(nums);\n        for (long f = max_n / nums[i]; f > 0; --f) {\n            auto it = lower_bound(begin(nums) + i, prev, f * nums[i]);\n            res = (res + k * f * (prev - it)) % 1000000007;\n            prev = it;\n        }\n    }\n    return res;\n}\n```\n#### Solution 4: Sieve\nSimilar aproach but flipped to quickly compute sums for all elements `[1.. n]`. It was proposed by [Ceay](https://leetcode.com/problems/sum-of-floored-pairs/discuss/1210057/Python-Five-lines-O(-n-log-n)). \n\n**C++ (160 ms)**\n```cpp\nint cnt[100001] = {}, sieve[100001] = {};\nint sumOfFlooredPairs(vector<int>& nums) {\n    int max_n = *max_element(begin(nums), end(nums));\n    for (auto n : nums)\n        ++cnt[n];\n    for (auto n = 1; n <= max_n; ++n)\n        if (cnt[n])\n            for (auto f = 1; n * f <= max_n; ++f)\n                sieve[f * n] += cnt[n];\n    partial_sum(begin(sieve), end(sieve), begin(sieve));\n    return accumulate(begin(nums), end(nums), 0, [&](int sum, int n) { return (sum + sieve[n]) % 1000000007; });\n}\n```
['C']