1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public:
const int MOD = 1000000007;
using LL = long long;
int sumOfFlooredPairs(vector<int>& nums) {
int upper = *max_element(nums.begin(), nums.end());
vector<int> s(upper + 1);
for (int x: nums) {
++s[x];
}
vector<int> pre(upper + 1);
for (int i = 1; i <= upper; ++i) {
s[i] += s[i - 1];
}
LL ans = 0;
for (auto i : nums) {
for (int j = 1; j * i <= upper; ++j) {
int l = j * i, r = min((j + 1) * i - 1, upper);
int sum = (LL) (s[r] - s[l - 1]) * j % MOD;
ans = (ans + (LL) sum) % MOD;
}
}
return ans;
}
};
|