【思维】GCD

加到v里面，另一半
倒着算这一个，减去倍数的

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
const ll N=100010;
ll a[N];
ll f[N];
ll n;ll m=100005;
vector<ll> v[N];int main(){
ll T;cin>>T;
while(T--){cin>>n;for(ll i=1;i<=m;i++)v[i].clear();for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);sort(a+1,a+n+1);for(ll j=1;j<=n;j++){for(ll i=1;i*i<=a[j];i++){if(a[j]%i==0){v[i].push_back(j);if (i!=a[j]/i){//不是平方v[a[j]/i].push_back(j);//另一半}}}}ll ans=0;memset(f,0,sizeof(f));for(ll i=m;i>=1;i--){for(ll j=0;j<v[i].size();j++){f[i]+=j*(n-v[i][j]);//j:第一个数[0,j-1] n-v[i][j]:第三个数，被忽略掉的最大数}for(ll j=2*i;j<=m;j+=i)f[i]-=f[j];//所以要倒着ans+=f[i]*i;}cout<<ans<<endl;
}
}