主要思路和推导

这道题还是比较有意思的（啊呀看了好久的题解才会写，真菜），主要就是把\(d\)转换成了：

\[ d(xy) = \sum_{i|x}^x \sum_{j|y}^y [\gcd(i,j) = 1] \]

可以感性理解一下：每一次约数被枚举出来的时候，只有互质的情况下才会被计数，避免了重复计数。

所以我们可以试着化简一下：

\[ \sum^N_{i=1} \sum^M_{j=1} d(i,j) = \sum^N_{i=1} \sum^M_{j=1} \sum_{x|i}^i \sum_{y|j}^j [\gcd(x,y) = 1] \\ \sum^N_{i=1} \sum^M_{j=1} \lfloor \frac{N}{i} \rfloor \lfloor \frac{M}{j} \rfloor [\gcd(x,y) = 1] \]

可以进行莫比乌斯反演了：

\[f(h) = \sum^N_{i=1} \sum^M_{j=1} \lfloor \frac{N}{i} \rfloor \lfloor \frac{M}{j} \rfloor [\gcd(x,y) = h] \\ F(h) = \sum_{h|d} f(h) \\ F(h) = \sum_{h|d} \sum^N_{i=1} \sum^M_{j=1} \lfloor \frac{N}{i} \rfloor \lfloor \frac{M}{j} \rfloor [\gcd(x,y) = d] \\ F(h) = \sum^N_{i=1} \sum^M_{j=1} \lfloor \frac{N}{i} \rfloor \lfloor \frac{M}{j} \rfloor [h|\gcd(x,y)] \\ F(h) = \sum^{\frac{N}{h}}_{i=1} \sum^{\frac{M}{h}}_{j=1} \lfloor \frac{N}{hi} \rfloor \lfloor \frac{M}{hj} \rfloor \\ f(h)=\sum_{h|d} \mu(\frac{d}{h})F(h) \\ f(h)=\sum_{h|d} \mu(\frac{d}{h}) \sum^{\frac{N}{h}}_{i=1} \sum^{\frac{M}{h}}_{j=1} \lfloor \frac{N}{hi} \rfloor \lfloor \frac{M}{hj} \rfloor \\ f(h)=\sum_{h|d} \mu(\frac{d}{h}) (\sum^{\frac{N}{h}}_{i=1} \lfloor \frac{N}{hi} \rfloor) (\sum^{\frac{M}{h}}_{j=1} \lfloor \frac{M}{hj} \rfloor) \]

后面的分数部分我们直接设个函数预处理即可：

\[ \sum^{\frac{N}{h}}_{i=1} \lfloor \frac{N}{hi} \rfloor = \sum^{\frac{N}{h}}_{i=1} \lfloor \frac{N}{h} * \frac{1}{i} \rfloor \]

可见得我们把\( \frac{N}{h} \)作为\(x\)，预处理出\(s(x) = \sum_{i=1}^x \frac{x}{i}\)，然后整除分块搞下复杂度就可以降到很低了。

代码

// P3327.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 50100;
int n, prime[MAX_N], tot, mu[MAX_N], muprefix[MAX_N];
ll g[MAX_N];
bool vis[MAX_N];
int main()
{
    scanf("%d", &n);
    mu[1] = 1;
    for (int i = 2; i < MAX_N; i++)
    {
        if (!vis[i])
            prime[++tot] = i, mu[i] = -1;
        for (int j = 1; j <= tot && i * prime[j] < MAX_N; j++)
        {
            vis[i * prime[j]] = true;
            if (i % prime[j] == 0)
                break;
            else
                mu[i * prime[j]] = -mu[i];
        }
    }
    for (int i = 1; i < MAX_N; i++)
        muprefix[i] = muprefix[i - 1] + mu[i];
    for (int i = 1; i < MAX_N; i++)
    {
        ll ans = 0;
        for (int l = 1, r = 0; l <= i; l = r + 1)
        {
            r = (i / (i / l));
            ans += 1LL * (r - l + 1) * 1LL * (i / l);
        }
        g[i] = ans;
    }
    while (n--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        ll ans = 0;
        for (int l = 1, r; l <= min(a, b); l = r + 1)
        {
            r = min(a / (a / l), b / (b / l));
            ans += (muprefix[r] - muprefix[l - 1]) * 1LL * g[a / l] * 1LL * g[b / l];
        }
        printf("%lld\n", ans);
    }
    return 0;
}