Source Code
/**
 *    author:  MaGnsi0
 *    created: 21.04.2022 11:20:38
**/
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        int64_t ans = 0, cnt_1 = 0;
        vector<int> F(N, 0);
        for (int i = 0; i < n; ++i) {
            ans += ((int64_t)(F[a[i]] + cnt_1) * (n - i));
            if (a[i] == 1) {
                cnt_1 += (i + 1);
                continue;
            }
            for (int j = a[i]; j < N; j += a[i]) {
                F[j] += (i + 1);
            }
        }
        cout << ans << "\n";
    }
}
Copy
Powerful Inversions MaGnsi0
GNU G++17
447 ms
1.1 MB
Wrong Answer