题意概述
给定长分别为 \(n,m\) 的数组 \(a,b\)，求：
\[\sum_{i=1}^{n}{\sum_{j=1}^{m}{\frac{lcm(a_i,b_j)}{gcd{(a_i,b_j)}}}}
\]
模 \(10^9+7\)。
思路
记值域为 \(V\)，\(cnt1[x]\) 为 \(a\) 中 \(x\) 出现次数，\(cnt2[y]\) 为 \(b\) 中 \(y\) 出现的次数。
原式为：
\[\sum_{x=1}^{V}{\sum_{y=1}^{V}{cnt1[x] \cdot cnt2[y] \cdot \frac{lcm(x,y)}{gcd(x,y)}}}
\]
将 \(lcm\) 化掉，得：
\[\sum_{x=1}^{V}{\sum_{y=1}^{V}{cnt1[x] \cdot cnt2[y] \cdot \frac{x}{gcd(x,y)} \cdot \frac{y}{gcd(x,y)}}}
\]
枚举 \(d=gcd(x,y)\)，得：
\[\sum_{d}{\sum_{x}^{V/d}{\sum_{y}^{V/d}{cnt1[xd] \cdot cnt2[yd] \cdot x y [gcd(x,y)=1]}}}
\]
根据莫比乌斯函数的性质，把 \(gcd(x,y)\) 化掉，得：
\[\sum_{d}{\sum_{x}^{V/d}{\sum_{y}^{V/d}{cnt1[xd] \cdot cnt2[yd] \cdot x y \cdot \sum_{k\mid gcd(x,y)}{\mu(k)}}}}
\]
交换求和，换元化简，得：
\[\sum_{d}{\sum_{k}{\mu(k)\cdot k^2 \left(\sum_{x}^{V/d/k}{cnt1[kdx]\cdot x}\right) \left(\sum_{y}^{V/d/k}{cnt2[kdy]\cdot y}\right) }}
\]
令 \(T=xd\)，得：
\[\sum_{T}^{V}{\left( \sum_{k\mid T}{\mu(k)\cdot k^2}\right) \left(\sum_{x}^{V/T}{cnt1[Tx]\cdot x}\right) \left(\sum_{y}^{V/T}{cnt2[Ty]\cdot y}\right)}
\]
令从左到右括号内式子分别为 \(f(x),g(x),h(x)\)。
原式就变成：
\[\sum_{T}^{V}{f(T)\cdot g(T) \cdot h(T)}
\]
\(g(x)\) 和 \(h(x)\) 可以在调和级数时间内暴力求出。
对于 \(f(x)\)，注意到 \(\mu(k)\cdot k^2\) 是积性函数，同时 \(f(x)\) 是狄利克雷卷积的形式，所以 \(f(x)\) 是积性函数，可以用欧拉筛在线性时间内求出。
时间复杂度 \(\mathcal{O}(T\cdot V\log V)\)。
代码
//author:kzssCCC#include <bits/stdc++.h>
using namespace std;
using ll = long long;const int V = 1e6;
const int MOD = 1e9+7;ll A[V+1],B[V+1],C[V+1];void init(){vector<bool> f(V+1,true);f[0] = f[1] = false;vector<int> prime;A[1] = 1;for (int i=2;i<=V;i++){if (f[i]){A[i] = (1-(ll)i*i%MOD+MOD)%MOD;prime.push_back(i);}for (auto& v:prime){if ((ll)v*i>V) break;f[v*i] = false;if (i%v==0){A[v*i] = A[i];break;}A[v*i] = A[v]*A[i]%MOD;}}
}void solve(){int n,m;cin >> n >> m;vector<int> a(n+1),cnt1(V+1);for (int i=1;i<=n;i++){cin >> a[i];cnt1[a[i]]++;}vector<int> b(m+1),cnt2(V+1);for (int i=1;i<=m;i++){cin >> b[i];cnt2[b[i]]++;}for (int t=1;t<=V;t++){B[t] = 0;for (int x=1;x<=V/t;x++){B[t] = (B[t]+x*cnt1[x*t]%MOD)%MOD;}C[t] = 0;for (int y=1;y<=V/t;y++){C[t] = (C[t]+y*cnt2[y*t]%MOD)%MOD;}}ll res = 0;for (int t=1;t<=V;t++){res = (res+A[t]*B[t]%MOD*C[t]%MOD)%MOD;}cout << res << '\n';
}int main(){ios::sync_with_stdio(false);cin.tie(0);init();int t;cin >> t;while (t--) solve();return 0;
}