inclusion exclusion

For a fixed g how many pairs that will have this g as a gcd, it'll be all multiples of g, it's easy to get the sum of multiplying those pairs.

but there is a problem with this, there will be some pairs that will be calculated multiple times, so we have to exclude the answer of (2 * g, 3 * g, ...), for example if we are solving when g = 2 we know that all the numbers divisible by 4 is also divisible by 2, so we have to exclude the answer of 4, and so on.

so the answer is iterate from the max number in descending order to 1 and solve for each fixed g, the total complexity of this solution is

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
const int mod = (int) 1e9 + 7;

int n, mx;
int a[N];
int cnt[N];
int ans[N];
long long inv[N];

void init() {
	inv[0] = inv[1] = 1;
	for (int i = 2; i < N; i++) {
		inv[i] = (mod - (mod / i) * inv[mod % i] % mod) % mod;
	}
}

int solve(int g) {
	long long sum = 0, res = 0;
	for (int i = g; i <= mx; i += g) {
		(sum += cnt[i] * 1LL * i % mod) %= mod;
	}
	for (int i = g; i <= mx; i += g) {
		(res += cnt[i] * 1LL * i % mod * sum % mod) %= mod;
	}
	(res *= inv[g]) %= mod;
	for (int i = 2 * g; i <= mx; i += g) {
		res -= ans[i] * 1LL * i % mod * inv[g] % mod;
		if (res < 0)
			res += mod;
	}
	return ans[g] = res;
}

int main() {
	init();
	int t;
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		memset(cnt, 0, sizeof cnt);
		memset(ans, 0, sizeof ans);
		mx = 0;
		for (int i = 0; i < n; i++) {
			scanf("%d", a + i);
			cnt[a[i]]++;
			mx = max(mx, a[i]);
		}
		int res = 0;
		for (int g = mx; g > 0; g--) {
			(res += solve(g)) %= mod;
		}
		printf("%d\n", res);
	}
	return 0;
}