Python3/C++ Fenwick Tree Solution 
ApproachFor each possible i<100000, we have the fact that:
numbers between i∗k and i∗(k+1)−1 gives k when divided by i
numbers between i∗(k+1) and i∗(k+2)−1 giv
# Approach
For each possible $i<100000$, we have the fact that:
- numbers between $i*k$ and $i*(k+1)-1$ gives $k$ when divided by $i$
- numbers between $i*(k+1)$ and $i*(k+2)-1$ gives $k+1$ when divided  by $i$
- and so on

We can use this fact to find each interval $[left,right]$ in which all numbers give k when divided by i. To find how many numbers is presenet in the interval $[left,right]$, we can use fenwick tree.  

   

# Complexity
- Time complexity: $O(n*sqrt(n)*log(n))$
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: $O(n)$
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
# Python3

```
mod=10**9+7
class Solution:
    def sumOfFlooredPairs(self, nums: List[int]) -> int:
        mx,res=max(nums),0
        tree=[0]*4*mx
        cnt=Counter(nums)

        def addVal(idx,val):
            idx+=1
            while idx<len(tree):
                tree[idx]+=val
                idx+=idx&(-idx)

        def getVal(idx):
            res,idx=0,idx+1
            while idx>0:
                res+=tree[idx]
                idx-=idx&(-idx)
            return res            

        for i in nums:
            addVal(i,1)

        for i in range(1,mx+1):
            freq=cnt[i]  
            if not freq:continue          
            for j in range(i,mx+1,i):                
                d=j//i                
                left,right=max(0,j),min(mx,j+i-1)                
                tot=getVal(right)-getVal(left-1)
                res+=freq*tot*d
                res%=mod

        return res
```

# C++

```
class Solution {
public:
    static constexpr int mod = 1'000'000'007;
    
    int sumOfFlooredPairs(vector<int>& nums) {
        int mx = *max_element(nums.begin(), nums.end());
        long long res = 0;
        vector<int> tree(4 * mx, 0);
        unordered_map<int, int> cnt;
        
        for (int num : nums) {
            cnt[num]++;
        }
        
        auto addVal = [&](int idx, int val) {
            idx++;
            while (idx < tree.size()) {
                tree[idx] += val;
                idx += idx & (-idx);
            }
        };
        
        auto getVal = [&](int idx) {
            long long sum = 0;
            idx++;
            while (idx > 0) {
                sum += tree[idx];
                idx -= idx & (-idx);
            }
            return sum;
        };
        
        for (int num : nums) {
            addVal(num, 1);
        }
        
        for (int i = 1; i <= mx; i++) {
            int freq = cnt[i];
            if (freq == 0) continue;
            
            for (int j = i; j <= mx; j += i) {
                int d = j / i;
                int left = max(0, j);
                int right = min(mx, j + i - 1);
                long long tot = getVal(right) - getVal(left - 1);
                res = (res + (long long)freq * tot * d) % mod;
            }
        }
        
        return res;
    }
};
```
['Python3']