题意：
求(sum_{i=1}^nsum_{j=1}^m mu({lcm(i,j)}))。
思路：
首先(lcm(i,j)=frac{ij}{gcd(i,j)})，不妨有(lcm(i,j))无平方因子，那么就有(gcd(frac{i}{gcd(i,j)},j))互质，所以(mu(lcm(i,j))=mu(i)mu(j)mu(gcd(i,j)))；如果(lcm(i,j))有平方因子的话，不影响答案。
注意(mu)的值和质因子个数有关，所以我们可以直接将"除以"写成"乘"。
下面就是推式子时间：
[egin{aligned}
&sum_{i=1}^n sum_{j=1}^m mu(lcm(i,j))\
=&sum_{i=1}^n sum_{j=1}^m mu(i) mu(j) mu(gcd(i,j))\
=&sum_dsum_isum_jmu(i)mu(j)mu(d) (gcd(i,j)=d)\
=&sum_dsum_{i=1}^{lfloorfrac{n}{d}
floor}sum_{j=1}^{lfloorfrac{m}{d}
floor} mu(id)mu(jd)mu(d) (gcd(i,j)=1)\
=&sum_dsum_{i=1}^{lfloorfrac{n}{d}
floor}sum_{j=1}^{lfloorfrac{m}{d}
floor} mu(id)mu(jd)mu(d)sum_{k|gcd(i,j)}mu(k)\
=&sum_{d=1}^{min(n,m)}sum_kmu(k)sum_{i=1}^{lfloorfrac{n}{dk}
floor}sum_{j=1}^{lfloorfrac{m}{dk}
floor}mu(ikd)mu(jkd)mu(d)
end{aligned}
]
令(T=kd,Tleq min(n,m))，则上式为：
[sum_Tsum_{d|T}mu(frac{T}{d})mu(d)sum_{i=1}^{lfloorfrac{n}{T}
floor}sum_{j=1}^{lfloorfrac{m}{T}
floor}mu(iT)mu(jT)
]
之后对于每个(T)，预处理(sum_dmu(frac{T}{d})mu(d))即可，时间复杂度(O(nlogn))。
后部分可以直接暴力，总时间复杂度为(O(Tnlogn))。
#include <bits/stdc++.h>
#define heyuhhh ok
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
int T;
int mu[N], p[N];
ll sum[N];
bool chk[N];
void init() {
mu[1] = 1;
int cnt = 0, k = N - 1;
for(int i = 2; i <= k; i++) {
if(!chk[i]) p[++cnt] = i, mu[i] = -1;
for(int j = 1; j <= cnt && i * p[j] <= k; j++) {
chk[i * p[j]] = 1;
if(i % p[j] == 0) {mu[i * p[j]] = 0; break;}
mu[i * p[j]] = -mu[i];
}
}
for(int i = 1; i <= k; i++) {
for(int j = i; j <= k; j += i) {
sum[j] += mu[i] * mu[j / i];
}
}
}
int n, m;
int main() {
#ifdef heyuhhh
freopen("input.in", "r", stdin);
#else
ios::sync_with_stdio(false); cin.tie(0);
#endif
init();
cin >> T;
while(T--) {
cin >> n >> m;
ll ans = 0;
for(int t = 1; t <= min(n, m); ++t) {
ll s1 = 0, s2 = 0;
for(int i = 1; i <= m / t; ++i) s1 += mu[i * t];
for(int i = 1; i <= n / t; ++i) s2 += mu[i * t];
ans += sum[t] * s1 * s2;
}
cout << ans << '
';
}
return 0;
}