这是一个需要欧拉反演的题目
首先，可以知道只和数字之间的大小有关，数列的顺序无关，那么就可以首先排一个序方便解决该问题。
根据欧拉函数的性质，知道\(n=\sum_{d|n}\phi{(n)}\)
那么我们每次先确定中间的数\(a_j\)，然后根据公式，得他它得贡献是\(\sum_{i=1}^{j-1}gcd(a_{i},a_{j})\)
用欧拉函数处理一下这个东西后面的\(gcd\)，然后得到\(\sum_{i=1}^{j-1}\sum_{d|a_{i}}\sum_{d|a_{j}}\phi{(d)}\)
交换一下求和的顺序，得到\(\sum_{d|a_{j}}\sum_{i=1}^{j-1}\sum_{d|a_{i}}\phi{(d)}\)，显然的，后面就是这个因数\(d\)的出现次数
所以可以化简为\(\sum_{d|a_{j}}cnt_{d}*\phi{(d)}\)
这个东西就可以很快的求出来了。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<vector>
#include<ctime>
#include<bitset>
#define int long long
using namespace std;
int phi[100005];
int not_prime[100005];
int prime[100005];
int p;
int a[100001];
long long ans;
void Eul(){
phi[1]=1;
not_prime[1]=0;
for(int i=2;i<=100000;++i){
if(!not_prime[i]){
prime[++p]=i;
phi[i]=i-1;
}
for(int j=1;j<=p&&i*prime[j]<=100000;++j){
not_prime[i*prime[j]]=1;
if(i%prime[j]==0){
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
phi[i*prime[j]]=phi[i]*phi[prime[j]];
}
}
}
int t;
int n;
int cnt[100005];
signed main(){
Eul();
scanf("%lld",&t);
while(t--){
memset(cnt,0,sizeof(cnt));
scanf("%lld",&n);
for(int i=1;i<=n;++i)
scanf("%lld",&a[i]);
sort(a+1,a+n+1);
ans=0;
for(int i=1;i<=n;++i){
long long tem=0;
for(int j=1;j*j<=a[i];j++){
if(a[i]%j!=0) continue;
tem+=phi[j]*cnt[j];
cnt[j]++;
if(j*j!=a[i]){
tem+=phi[a[i]/j]*cnt[a[i]/j];
cnt[a[i]/j]++;
}
}
ans+=tem*(n-i);
}
printf("%lld\n",ans);
}
return 0;
}