1862. Sum of Floored Pairs

Given an integer array nums, return the sum of floor(nums[i] / nums[j]) for all pairs of indices 0 <= i, j < nums.length in the array. Since the answer may be too large, return it modulo 109 + 7.

The floor() function returns the integer part of the division.

class Solution {
public:
    int sumOfFlooredPairs(vector<int>& A) {
        sort(begin(A), end(A));
        int res = 0, n = A.size(), prevRes = 0, mod = 1e9 + 7;
        for(int i = 0, p, st = 0; i < n; st = ++i) {
            if(!i or A[i] != A[i-1]) {
                prevRes = 0;
                while(st < n) {
                    p = (A[st] / A[i]) + 1;
                    int nxt = lower_bound(begin(A) + st, end(A), A[i] * p) - begin(A);
                    prevRes = (prevRes + (nxt - st) * (p - 1)) % mod;
                    st = nxt;
                }
            }
            res = (res + prevRes) % mod;
        }
        
        
        return res;
    }
};