1
class Solution {
2
 private:
3
  int MOD = 1e9 + 7;
4

5
 public:
6
  int sumOfFlooredPairs(vector<int> &nums) {
7
    // first of all, we record the max value
8
    int max_n = INT_MIN;
9
    for (int n : nums) max_n = max(max_n, n);
10

11
    // then the occurences for each number in [0, max]
12
    vector<int> occs(max_n + 1, 0);
13
    for (int n : nums) occs[n]++;
14

15
    // prefix sum algorithm to accumulate the occurences
16
    vector<int> occs_acc(max_n + 1, 0);
17
    for (int i = 1; i < max_n + 1; ++i) {
18
      occs_acc[i] = occs[i] + occs_acc[i - 1];
19
    }
20

21
    // long long needed to prevent overflows
22
    long long ans = 0;
23
    for (int i = 0; i < max_n + 1; ++i) {
24
      // just handle numbers that occur at least once
25
      if (occs[i] != 0) {
26
        int k = 1;
27
        int k_next;
28

29
        // for each multiple of i
30
        do {
31
          k_next = k + 1;
32

33
          // "right and left" multipliers in occs_acc
34
          int r = min(k_next * i - 1, max_n);
35
          int l = k * i - 1;
36

37
          ans += ((long long)occs_acc[r] - (long long)occs_acc[l]) * (long long)occs[i] * k++;
38

39
        } while (k_next * i - 1 < max_n);
40
      }
41
    }
42

43
    return ans % MOD;
44
  }
45
};