萌萌柿子题。
定义 \(\mathbb{P}\) 为适当大小的质数集，\(P(x) = [x \in \mathbb{P}]\)。
\[\begin{align*}
&~~~~~\sum_{x = 1} ^ {N} \sum _ {y = 1} ^ {M}\left [ \gcd(x, y) \in \mathbb{P} \right]\\
&= \sum_{p = 1, p \in \mathbb{P}}\sum_{x = 1} ^ {N} \sum _ {y = 1} ^ {M} [\gcd(x, y) = p]\\
&= \sum_{p = 1, p \in \mathbb{P}}\sum_{x = 1} ^ {\left\lfloor \frac{N}{p} \right\rfloor} \sum _ {y = 1} ^ {\left\lfloor \frac{M}{p} \right\rfloor} [\gcd(x, y) = 1]\\
\end{align*}
\]
发现后面那一坨可以转换成 \(\mu\) 函数的格式。
\[\begin{align*}
&= \sum_{p = 1, p \in \mathbb{P}}\sum_{x = 1} ^ {\left\lfloor \frac{N}{p} \right\rfloor} \sum _ {y = 1} ^ {\left\lfloor \frac{M}{p} \right\rfloor} \sum_{d | \gcd(x, y)}\mu(d) \\
&= \sum_{p = 1, p \in \mathbb{P}} \sum_{d = 1} ^ {\left\lfloor \frac{\max(N, M)}{p} \right\rfloor}\mu(d) \sum_{x = 1} ^ {\left\lfloor \frac{N}{dp} \right\rfloor} \sum _ {y = 1} ^ {\left\lfloor \frac{M}{dp} \right\rfloor} 1 \\
&= \sum_{p = 1, p \in \mathbb{P}} \sum_{d = 1} ^ {\left\lfloor \frac{\max(N, M)}{p} \right\rfloor}\mu(d) \left\lfloor \frac{N}{dp} \right\rfloor \left\lfloor \frac{M}{dp} \right\rfloor \\
&= \sum _ {d = 1} ^ {\max(N, M)} \left \lfloor \frac{N}{d} \right \rfloor\left \lfloor \frac{M}{d} \right \rfloor \sum _ {p \mid d, p \in \mathbb{P}} \mu\left(\frac{d}{p}\right)\\
&= \sum _ {d = 1} ^ {\max(N, M)} \left \lfloor \frac{N}{d} \right \rfloor\left \lfloor \frac{M}{d} \right \rfloor \sum _ {p \mid d} P(p) \times \mu\left(\frac{d}{p}\right)\\
&= \sum _ {d = 1} ^ {\max(N, M)} \left \lfloor \frac{N}{d} \right \rfloor\left \lfloor \frac{M}{d} \right \rfloor \left(P \times \mu\right)(d)
\end{align*}
\]
后面那一坨就是狄利克雷卷积，然而我不会就自己想了一个做法。
对于每一个 \(d\) 预处理 \((P \times \mu)(d)\) 的值。
整除分块一下，此时同一个块里面 \(\left \lfloor \frac{N}{d} \right \rfloor\left \lfloor \frac{M}{d} \right \rfloor\) 是相同的，所以可以把该式提出来，后面的一坨就可以用前缀和预处理。
我也不知道狄利克雷卷积怎么算（总不能就这么算吧），反正这样足以通过此题。
预处理时间复杂度 \(\mathcal{O} (n)\)，分块的时间复杂度 \(\mathcal{O}(\sqrt{n})\)，所以总时间复杂度为 \(\mathcal{O}(n + T\sqrt{n})\)。
#include <bits/stdc++.h>
#define int long long
#define pii pair< int, int >
#define FRE(x) freopen(x ".in", "r", stdin), freopen(x ".out", "w", stdout)
#define L(i, a, b) for (register int i = (a); i <= (b); i++)
#define R(i, a, b) for (register int i = (a); i >= (b); i--)
#define ALL(x) x.begin(), x.end()
using namespace std;inline void cmax(int &x, int c) { x = max(x, c); }
inline void cmin(int &x, int c) { x = min(x, c); }int _test_ = 1;namespace code {const int N = 2e7 + 6;int mu[N], f[N], sum[N], p[N], cnt;bool vis[N];void init() {mu[1] = 1;L(i, 2, N - 6) {if (! vis[i]) p[++cnt] = i, mu[i] = -1;for (int j = 1; j <= cnt && i * p[j] <= N - 6; j++) { // 线性筛，同时预处理 muvis[i * p[j]] = 1;if (i % p[j] == 0) break;mu[i * p[j]] = (-1) * mu[i];}}L(i, 1, cnt) {L(j, 1, N - 6) {if (j * p[i] > N - 6) break;f[j * p[i]] += mu[j]; // 处理卷积得到的函数}}L(i, 1, N - 6) sum[i] = sum[i - 1] + f[i]; // 前缀和// L(i, 1, N - 6) cout << f[i] << " ";}void clear() {}void solve() {int n, m;cin >> n >> m;int ans = 0;if (n > m) swap(n, m);L(i, 1, n) {int j = min(n / (n / i), m / (m / i)); // 整除分块ans += (sum[j] - sum[i - 1]) * (int)(n / i) * (int)(m / i);i = j;}cout << ans << "\n";}} // namespace codesigned main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> _test_;code::init();L(i, 1, _test_) {code::clear();code::solve();}return 0;
}