Explained Clean Code | Beats 100% 23ms
IntuitionSimilar to the Sieve of Eratosthenes, this solution uses a frequency-based counting approach to compute floor division contributions across all array p
# Intuition
Similar to the Sieve of Eratosthenes, this solution uses a frequency-based counting approach to compute floor division contributions across all array pairs.

# Approach
The key insight is transforming the problem from pair-wise computation to a frequency-based counting strategy:

1. **Frequency Accumulation**:
   - Count occurrences of each number
   - Create a prefix sum of frequencies from right to left
   - This allows O(1) access to count of numbers ≥ a given value

2. **Incremental Contribution**:
   - Iterate through numbers from maximum to minimum
   - For each number, compute its contribution to floor division
   - Use accumulated frequencies to quickly calculate multiples impact

# Intuitive Explanation
Imagine you want to count how many times you can divide different numbers in your array by a specific number. Instead of checking every single pair (which would take forever), we:
1. First count how many of each number we have
2. Then calculate how many times we can divide by each possible divisor
3. Accumulate these results step by step

# Complexity
- **Time Complexity**: $$O(M \log M)$$, where M is maximum array value
  - Frequency computation: O(N)
  - Multiples computation: O(M log M)
- **Space Complexity**: $$O(M)$$

# Code
```cpp []
class Solution {
public:
    int sumOfFlooredPairs(vector<int>& nums) {
        // 1. Pure count: O(M*log(M)) - best for dense, small-range inputs
        return sumOfFlooredPairs_pure_count(nums); // 23ms
        // 2. Multiples sliding: O(N*log(N)) - flexible for sparse inputs
        return sumOfFlooredPairs_multiples_fw_slide(nums); // 700ms

        return sumOfFlooredPairs_seg_end_slide(nums); // TL
    }

    int sumOfFlooredPairs_pure_count(const vector<int>& nums) {
        // Compute accumulated count per value
        long long* acc_count = buf.data();
        long long M = nums[0];
        for (long long n : nums) {
            ++acc_count[n];
            M = max(M, n);
        }
        for (int i = M - 1; ~i; --i)
            acc_count[i] += acc_count[i + 1];

        long long res = 0;

        for (long long i = M; ~i; --i) {
            const long long count = acc_count[i] - acc_count[i + 1]; // De-accumulate
            if (count) {
                long long sum = 0;
                for (long long m = i; m <= M; m += i)
                    sum += acc_count[m];
                    // NB: Theoretically the above m=i*k contributes k = i*k / i but all
                    // lower [k-1..1] we have handled before because we use acc_count not count
                    // So this is incremental contribution
                res = (res + sum * count) % kMod;
            }
        }

        memset(acc_count, 0, sizeof(long long) * (M + 1)); // Reset buffer for next computation
        return res;
    }

    int sumOfFlooredPairs_multiples_fw_slide(vector<int>& nums) {
        // Derive pairs: value and accumulated count in value descend order
        sort(nums.begin(), nums.end());
        vector<pair<long long, long long>> val_acc_count(nums.size());
        val_acc_count.clear();
        for (int end = nums.size() - 1, i = nums.size() - 2; i > -2; --i) {
            if (i < 0 || nums[i] < nums[i + 1]) {
                val_acc_count.emplace_back(
                    nums[i + 1],
                    (end - i + (val_acc_count.empty() ? 0LL : val_acc_count.back().second)) % kMod);
                end = i;
            }
        }

        long long res = 0;

        for (auto rit = val_acc_count.rbegin(); rit != val_acc_count.rend(); ++rit) {
            long long seg_len = rit->second;
            auto pr = next(rit);
            if (pr != val_acc_count.rend())
                seg_len -= pr->second;
            // Find multiples and compute sums
            for (long long m = rit->first; ; m += rit->first) {
                auto rseg_end = lower_bound(
                    rit, val_acc_count.rend(), m,
                    [](const auto& elem, long long tgt) { return elem.first < tgt; });
                if (rseg_end == val_acc_count.rend()) break;
                // NB: Theoretically the above m=rit->first*k contributes
                // k = rit->first*k / rit->first but all lower [k-1..1] we have handled before
                // because we use rseg_end->second = accumulated count
                res += seg_len * rseg_end->second;
            }
            res %= kMod;
        }

        return res;
    }

    int sumOfFlooredPairs_seg_end_slide(vector<int>& nums) {
        sort(nums.begin(), nums.end());

        long long res = 0;

        for (auto seg_beg = nums.begin(); seg_beg != nums.end(); ) {
            // End of segment with same value
            auto seg_end = upper_bound(seg_beg, nums.end(), *seg_beg);
            long long seg_len = distance(seg_beg, seg_end);
            res += seg_len * seg_len; // Self-division contributions

            // Floor divisions with previous segments
            auto p = nums.begin();
            while (p != seg_beg) {
                long long r = *seg_beg / *p;
                auto q = upper_bound( // The same r will be on whole range [p..q)
                    p, seg_beg, r, [sb = *seg_beg](int r, int e) { return r > sb / e; });
                long long len = distance(p, q);
                res += len * r * seg_len;
                p = q;
            }

            res %= kMod;
            seg_beg = seg_end;
        }

        return res;
    }

private:
    static constexpr long long kMod = 1e9 + 7;
    static constexpr int kMaxNum = 1e5;

    static array<long long, kMaxNum + 2> buf;
};

array<long long, Solution::kMaxNum + 2> Solution::buf{};

```
['C++']