### nik1996's blog

By nik1996, 5 weeks ago, , Hello all, Recently I was attempting the following problem: Given an array of integers, arr. Find sum of floor of (arr[i]/arr[j]) for all pairs of indices (i,j).

e.g. arr[]={1,2,3,4,5}, Sum=27.

I could only think of naive O(n^2) solution. Is there any other better approach? Comments (6)
•  » » » » 5 weeks ago, # ^ | ← Rev. 3 →   Code with a little commentconst int MX = 100005; int cnt[MX], b[MX]; int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); ios_base :: sync_with_stdio(0); cin.tie(0), cout.tie(0); int n, x; cin >> n; for (int i = 1; i <= n; i++) { cin >> x; cnt[x]++; } for (int i = MX - 1; i >= 1; i--) { b[i] = b[i + 1] + cnt[i]; } long long res = 0; for (int i = 1; i < MX; i++) { if (cnt[i] == 0) { continue; } for (int j = i, mul = 1; j < MX; j += i, mul++) { /// there are b[j] - b[j + i] elements which adds mul to the ans res += 1LL * (b[j] - b[min(MX - 1, j + i)]) * mul * cnt[i]; /// *cnt[i] because we have cnt[i] times i } } cout << res << endl; return 0; } Note: I assume there are no same elements in the array. Otherwise, the code can easily be modified.