[C++, 240ms] Prefix sum * frequency with explanation
Basic idea: ranges for the numerators. E.g. 4/4..7/4=1, 8/4..11/4=2. Multiply by count(4..7)*count(4) for the first, count(8..11)*count(4) for the second, etc.\
Basic idea: ranges for the numerators. E.g. 4/4..7/4=1, 8/4..11/4=2. Multiply by `count(4..7)*count(4)` for the first, `count(8..11)*count(4)` for the second, etc.\n\n```\nclass Solution {\npublic:\n    int sumOfFlooredPairs(vector<int>& nums) {\n        const int M = 1e9 + 7;\n        const int N = 1e5 + 1;\n        \n\t\t// Frequency of nums\n        std::vector<int> freq(N + 1, 0);\n        \n        int max_num = 0;\n        for (auto i : nums) {\n            max_num = std::max(i, max_num);\n            ++freq[i];\n        }\n        \n\t\t// Prefix sum of frequencies\n        std::vector<int> prefix_freq(max_num + 1, 0);  \n        prefix_freq[0] = freq[0];\n        for (int i = 1; i <= max_num; i++)\n            prefix_freq[i] = prefix_freq[i - 1] + freq[i];\n\n        long res = 0;\n\t\t// Check denominators in nums\n        for (int den = 1; den <= max_num; ++den) {\n            if (!freq[den])\n                continue;\n            \n            long mul = 1;\n            int n0 = den;\n            int n1 = 2 * den - 1;\n\t\t\t// (n0 to n1)/d = mul, (n1+1)/d = mul + 1\n            while (n0 <= max_num) {                \n                int f0 = prefix_freq[n0 - 1];\n                int f1 = prefix_freq[std::min(max_num, n1)];\n                \n\t\t\t\t// res += (n0 to n1)/d * freq(den) * freq(n0..n1-1)\n                res += mul * freq[den] * (f1 - f0);\n                res %= M;\n                \n                ++mul;\n                n0 += den;\n                n1 += den;\n            }\n        }\n        \n        return res;\n    }\n};\n```
[]