sum-of-floored-pairs.cpp

// Time:  O(n/1+n/2+...+n/n) = O(nlogn), n is the max of nums
// Space: O(n)

class Solution {
public:
    int sumOfFlooredPairs(vector<int>& nums) {
        static const int MOD = 1e9 + 7;
        vector<int> prefix(*max_element(cbegin(nums), cend(nums)) + 1);
        unordered_map<int, int> count;
        for (const auto& num : nums) {
            ++count[num];
        }
        for (const auto& [num, cnt] : count) {
            for (int j = num; j < size(prefix); j += num) {
                prefix[j] += cnt;
            }
        }
        for (int i = 0; i + 1 < size(prefix); ++i) {
            prefix[i + 1] += prefix[i];
        }
        return accumulate(cbegin(nums), cend(nums), 0,
                          [&prefix](int total, int x) {
                              return (total + prefix[x]) % MOD;
                          });
    }
};