111
排序之后
我们可以枚举最大值 因为之前的任意两个gcd都不能超过这个最大值
但是 我们每次往下枚举 就要加入这个最大值
我们可以枚举他的因子 要是之前出现过 那么这个因子的贡献显然就可以求出来
但是这样有可能 多算了贡献比如 20可能算到 20 也算了 2
我们设sum_i 表示gcd为i的倍数时的贡献
随后直接经典容斥即可
vector<int>factor[100010];
void solve(){
int n;cin>>n;
vector<int>a(n+1),sum(100010),cnt(100010);
for(int i=1;i<=n;i++)cin>>a[i];
sort(a.begin()+1,a.end());
int ans=0;
for(int i=1;i<=n;i++){
for(auto t:factor[a[i]]){
sum[t]+=cnt[t]*(n-i);
cnt[t]++;
}
}
for(int i=a[n];i>=1;i--){
for(int j=2*i;j<=1e5;j+=i){
sum[i]-=sum[j];
}
ans+=sum[i]*i;
}
cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
for(int i=1;i<=1e5;i++){
for(int j=i;j<=1e5;j+=i){
factor[j].push_back(i);
}
}
int t=1;cin>>t;
while(t--)solve();
}