众所周知，这题不是个人也会。
$$ \text{首先可知}d\left( nm \right) =\sum_{a|n}{\sum_{b|m}{\left[ \mathrm{gcd}\left( a,b \right) =1 \right]}} \\ \sum_{1\le i\le n}{\sum_{1\le j\le m}{\sum_{a|i}{\sum_{b|j}{\left[ \mathrm{gcd}\left( a,b \right) =1 \right]}}}} \\ =\sum_{1\le i\le n}{\sum_{1\le j\le m}{\sum_{a|i}{\sum_{b|j}{\sum_{k|gcd\left( a,b \right)}{\mu \left( k \right)}}}}} \\ =\sum_{1\le k\le n}{\mu \left( k \right) \sum_{1\le i\le n}{\sum_{1\le j\le m}{\sum_{a|i}{\sum_{b|j}{\left[ k|\mathrm{gcd}\left( a,b \right) \right]}}}}} \\ =\sum_{1\le k\le n}{\mu \left( k \right) \sum_{1\le a\le n}{\sum_{1\le b\le m}{\sum_{a|i,i\le n}{\sum_{b|j,j\le m}{\left[ k|gcd\left( a,b \right) \right]}}}}} \\ a\gets ak,b\gets bk \\ =\sum_{1\le k\le n}{\mu \left( k \right) \sum_{1\le ak\le n}{\sum_{1\le bk\le m}{\left[ k|gcd\left( ak,bk \right) \right] \lfloor \frac{n}{ak} \rfloor \lfloor \frac{m}{bk} \rfloor}}} \\ =\sum_{1\le k\le n}{\mu \left( k \right) \sum_{1\le a\le \lfloor \frac{n}{k} \rfloor}{\sum_{1\le b\le \lfloor \frac{m}{k} \rfloor}{\lfloor \frac{n}{ak} \rfloor \lfloor \frac{m}{bk} \rfloor}}} \\ =\sum_{1\le k\le n}{\mu \left( k \right) \sum_{1\le a\le \lfloor \frac{n}{k} \rfloor}{\sum_{1\le b\le \lfloor \frac{m}{k} \rfloor}{\lfloor \frac{\lfloor \frac{n}{k} \rfloor}{a} \rfloor \lfloor \frac{\lfloor \frac{m}{k} \rfloor}{b} \rfloor}}} \\ =\sum_{1\le k\le n}{\mu \left( k \right) \left( \sum_{1\le a\le \lfloor \frac{n}{k} \rfloor}{\lfloor \frac{\lfloor \frac{n}{k} \rfloor}{a} \rfloor} \right) \left( \sum_{1\le b\le \lfloor \frac{m}{k} \rfloor}{\lfloor \frac{\lfloor \frac{m}{k} \rfloor}{b} \rfloor} \right)} \\ S\left( n \right) =\sum_{1\le i\le n}{\lfloor \frac{n}{i} \rfloor} \\ \text{原式}=\sum_{1\le k\le n}{\mu \left( k \right) S\left( \lfloor \frac{n}{k} \rfloor \right) S\left( \lfloor \frac{m}{k} \rfloor \right)} \\ $$
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using int_t = long long int;
const int_t LARGE = 5e4;
using std::cin;
using std::cout;
using std::endl;
int_t S[LARGE + 1];
bool isPrime[LARGE + 1];
int_t factor[LARGE + 1];
int_t mu[LARGE + 1];
int_t muSum[LARGE + 1];
int_t Sx(int_t n) {
int_t result = 0;
int_t i = 1;
while (i <= n) {
int_t next = n / (n / i);
result += (next - i + 1) * (n / i);
i = next + 1;
}
return result;
}
int_t query(int_t n, int_t m) {
if (n > m)
std::swap(n, m);
int_t result = 0;
int_t i = 1;
while (i <= n) {
int_t next = std::min(n / (n / i), m / (m / i));
result += (muSum[next] - muSum[i - 1]) * S[n / i] * S[m / i];
i = next + 1;
}
return result;
}
int main() {
for (int_t i = 1; i <= LARGE; i++) {
S[i] = Sx(i);
}
memset(isPrime, 1, sizeof(isPrime));
for (int_t i = 2; i <= LARGE; i++) {
if (isPrime[i]) {
factor[i] = i;
for (int_t j = i * i; j <= LARGE; j += i) {
isPrime[j] = false;
if (!factor[j])
factor[j] = i;
}
}
}
mu[1] = muSum[1] = 1;
for (int_t i = 2; i <= LARGE; i++) {
int_t factor = ::factor[i];
if (i / factor % factor == 0)
mu[i] = 0;
else
mu[i] = mu[i / factor] * -1;
muSum[i] = muSum[i - 1] + mu[i];
}
int T;
scanf("%d", &T);
while (T--) {
int n, m;
scanf("%d%d", &n, &m);
auto result = query(n, m);
printf("%lld\n", result);
}
return 0;
}