Source Code
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ordered_multiset tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ordered_multiset2 tree<pair<int,int>, null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update>
int oms=0;
//find_by_order() -> first
//order_of_key() {}

#define fs(n) fixed<<setprecision(n)
#define all(v) v.begin(),v.end()
#define ll long long
#define f first
#define s second
#define nl cout<<"\n"
#define ci(v) for(auto&it:v){cin>>it;}
#define ci1(v) for(int inddd=1;inddd<v.size();inddd++){cin>>v[inddd];}
#define cp(v) for(auto&it:v){cin>>it.first>>it.second;}
#define cii(n,m,v) for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>v[i][j];}}
#define dbp(v) for(auto it:v)cout<<it.first<<" "<<it.second<<"\n";
#define dbi cout<<"(lol)\n"
#define db(n) cout<<"("<<n<<")\n"
#define dbb(x,y) cout<<"("<<x<<" "<<y<<")\n"
#define dbbb(x,y,z) cout<<"("<<x<<" "<<y<<" "<<z<<")\n"
#define dbbbb(a,b,c,d) cout<<"("<<a<<" "<<b<<" "<<c<<" "<<d<<")\n"
#define dbv(v) for(auto it:v){cout<<it<<" ";}cout<<"\n"
#define dbvp(v) for(int i=0;i<v.size();i++){cout<<v[i].first<<" "<<v[i].second<<"\n";}
#define dbs(se) cout<<"/*";for(auto it:se){cout<<it<<" ";}cout<<"*/\n";
#define dbvv(n,m,v) for(int i=0;i<n;i++){if(i==0){cout<<"\n\\\\\\\\\\\\\\\\\n";}for(int j=0;j<m;j++){cout<<v[i][j]<<" ";}cout<<"\n";if(i==n-1){cout<<"\\\\\\\\\\\\\\\\\n";}}
#define dbbv(v) cout<<"\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\n";for(auto it:v){for(auto it2:it){cout<<it2<<" ";}cout<<"\n";}cout<<"\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\n"
long long gcd(long long x,long long y){return(!y?x:gcd(y,x%y));}
typedef pair<int,int>pii;
typedef vector<bool>vb;
typedef vector<int>vi;
typedef vector<long long>vl;
typedef vector<vi>vvi;
typedef vector<vl>vvl;
typedef vector<pii>vii;
typedef vector<vector<pii>>vvii;

const long long mod=1e9+7;
int r[]= {0,0,1,-1};
int c[]= {1,-1,0,0};

long long fp(long long base,long long power){
long long ans=1;
while(power>0){
if(power&1)ans=(ans*base)%mod;
base=(base*base)%mod;
power>>=1;
}
return ans;
}

long long po(long long base,long long power)
{
    long long ans=1;
    while(power>0)
    {
        if(power&1)ans*=base;
        base*=base;
        power>>=1;
    }
    return ans;
}

long long lcm(long long a,long long b)
{
    return (a*b)/gcd(a,b);
}

long long fopis(long long n,long long p){
if(p>(n+1)/2)p=n-p+1;
return n-1+((p-1)*((n+n-4)+((p-2)*(-2))))/2;
}

void sol(int tcn){

long long n,x,mx=0,ans=0;
cin>>n;
vector<vector<long long>>mp(100001);
vector<long long>v(n);
for(int i=0;i<n;i++){
    cin>>v[i];
    mx=max(mx,v[i]);
    mp[v[i]].push_back(i);
}
for(long long i=0;i<n;i++){
    if(v[i]!=0)
    for(int j=v[i]+v[i];j<=mx;j+=v[i]){
        int sz=mp[j].size();
        auto it=upper_bound(mp[j].begin(),mp[j].end(),i);
        if(it!=mp[j].end()){
            int ind=(it-mp[j].begin());
            for(int k=ind;k<sz;k++){
                ans=ans+((n-mp[j][k]-1LL)*i)+i+(n-mp[j][k]-1LL)+1LL;
            }
        }
    }
}
for(int i=1;i<=100000;i++){
    long long sum=0,sz=mp[i].size();
    for (int j=0;j<sz;j++){
        ans=ans+(sum*(n-mp[i][j]));
        sum=sum+mp[i][j]+1LL;
    }
}
cout<<ans;

}

int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

int t=1,tcn=1;
cin>>t;
while(t--){
    sol(tcn++);
    if(t!=0)cout<<"\n";
}

return 0;
}
Copy
Powerful Inversions AshrafYousry
GNU G++17
3091 ms
2.7 MB
Time Limit Exceeded