Source Code
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int OO = 1e9+7 ,N=1e6+5;

int dx[] = { 0, 0, 1, -1, 1, -1, 1, -1 }; // dir array
int dy[] = { 1, -1, 0, 0, 1, -1, -1, 1 };
void File(){
#ifndef ONLINE_JUDGE
    freopen("Input.txt", "r", stdin);
    freopen("Output.txt", "w", stdout);
#endif
}
vector<int>getdiv(int n){
    vector<int>v;
    for(int i=1;i*i<=n;i++){
        if(n%i==0){
            v.push_back(i);
            if(i*i!=n)v.push_back(n/i);
        }
    }
    sort(v.begin(),v.end());
    return v;
}
int kk;
int solve(int k){
    ll n;cin>>n;
    vector<int>a(n);
    map<int,int>mp;
    for(int &i:a)cin>>i;
    ll ans=0;
    set<pair<int,int>>st,st2;
    for(int i=0;i<n;i++){
        vector<int>v= getdiv(a[i]);
        for(auto j:v){
            ll idx=-1,idx2=-1;
            auto lb2= st2.lower_bound({j,-OO}),
            lb = st.lower_bound({j,-1});
            if(lb2!=st2.end() && lb2->first ==j)idx2=-lb2->second;
            if(lb!=st.end() && lb->first ==j)idx=lb->second;
            idx++,idx2++;
            ll num=idx2-idx+1;
            num = (num*num+num)/2;
//            cout<<idx<<' '<<idx2<<endl;
            ans += idx * (n-i) *num;
        }
//        cout<<endl;
        st.insert({a[i],i});
        st2.insert({a[i],-i});
    }
    if(k==53&&kk==10000){
        cout<<n<<' ';for(auto i:a)cout<<i<<' ';cout<<endl;
        return 0;
    }
    cout<<ans<<'\n';
    return 0;
}
int main() {
    File();
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t,i=1;cin>>t;kk=t;
    while(t--)
        solve(i++);

}
//Solve on paper first
//Overflooooooow
//Reverse Thinking
//If there's an equation, transform it into an easy one
//READ ALL PROBLEMS
//Verify Your thought before Coding
Copy
Powerful Inversions ahmes
GNU G++17
37 ms
312 KB
Wrong Answer