1
class Solution {
2
  public int sumOfFlooredPairs(int[] nums) {
3
    Arrays.sort(nums);
4
    int n = nums.length;
5
    long cnt[] = new long[nums[n - 1] + 2];
6
    for (int num : nums) {
7
      cnt[num + 1]++;
8
    }
9
    for (int i = 1; i < cnt.length; i++) {
10
      cnt[i] += cnt[i - 1];
11
    }
12
    long res = 0;
13
    long mod = 1000000007;
14
    long dp[] = new long[cnt.length];
15
    for (int num : nums) {
16
      if (dp[num] != 0) {
17
        res = (res + dp[num]) % mod;
18
        continue;
19
      }
20
      long tot = 0;
21
      for (int j = num; j < cnt.length - 1; j += num) {
22
        tot = (tot + (j / num) * (cnt[Math.min(j + num - 1, nums[n - 1]) + 1] - cnt[j])) % mod;
23
      }
24
      dp[num] = tot;
25
      res = (res + tot) % mod;
26
    }
27
    return (int) res;
28
  }
29
}