Source Code
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include <stdio.h>
#define ll long long
#define mem(a,n) memset((a),n,sizeof (a))
void fast();
ll gcd(ll x, ll y) { return(!y ? x : gcd(y, x % y)); }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
int dx[]{ 1, -1, 0, 0, 1, 1, -1, -1 };
int dy[]{ 0, 0, 1, -1, 1, -1, 1, -1 };
using namespace std;
int main()
{
    //freopen("input.txt" ,"r" ,stdin);
   //freopen("output.txt" ,"w" ,stdout);
    fast();
    int t; cin >> t;
    vector<vector<int>>f(1e5 + 5);
    for (int i = 1; i <= 1e5; i++) {
        f[i].push_back(1); if (i != 1)f[i].push_back(i);
        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                f[i].push_back(j);
                if (j * j != i)f[i].push_back(i / j);
            }
        }
    }
    while (t--) {
        int n; cin >> n;
        vector<ll>v(100000 + 5); vector<int> v2(n + 5);
        for (int i = 1; i <= n; i++) {
            cin >> v2[i];
            for (int j = 0; j < f[v2[i]].size(); j++) {
                v[f[v2[i]][j]] += n - i + 1;
            }
        }

        ll ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < f[v2[i]].size(); j++) {
                v[f[v2[i]][j]] -= (n - i + 1);
            }
            ans += (ll)i * v[v2[i]];
        }
        cout << ans << "\n";
    }

    return 0;
}
void fast() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
Copy
Powerful Inversions Nourhan Hanna
GNU G++17
561 ms
11.0 MB
Accepted