由于\(NM\)的约数一定可以写成\(\frac{pM} {q}(p \mid N ,q \mid M)\)的形式,我们有：
\[d(NM)=\sum_{p\mid N}\sum_{q\mid M}[\gcd(p,q)=1]\]
代入原式：
\[\begin{aligned}\sum_{i=1}^{N}\sum_{j=1}^{M}d(ij)&=\sum_{i=1}^{N}\sum_{j=1}^{M}\sum_{p \mid i}\sum_{q \mid j}[\gcd(p,q)=1] \\ &=\sum_{i=1}^{N}\sum_{j=1}^{M}\left \lfloor \frac {N} {i} \right \rfloor \left \lfloor \frac {M} {j} \right \rfloor[\gcd(i,j)=1] \\ &=\sum_{i=1}^{N}\sum_{j=1}^{M}\left \lfloor \frac {N} {i} \right \rfloor \left \lfloor \frac {M} {j} \right \rfloor\sum_{d \mid \gcd(i,j)}\mu(d) \\ &=\sum_{d=1}^{N} \mu(d) \sum_{i=1}^{\left \lfloor \frac {N} {d} \right \rfloor}\sum_{j=1}^{\left \lfloor \frac {M} {d} \right \rfloor }\left \lfloor\frac{N}{id}\right\rfloor\left \lfloor\frac{M}{jd}\right\rfloor \\ &=\sum_{d=1}^{N} \mu(d) \sum_{i=1}^{\left \lfloor \frac {N} {d} \right \rfloor} \left \lfloor\frac{N}{id}\right\rfloor\sum_{j=1}^{\left \lfloor \frac {M} {d} \right \rfloor }\left \lfloor\frac{M}{jd}\right\rfloor\end{aligned}\]
设\(g(n)=\sum_{i=1}^{n}\left \lfloor \frac {n} {i}\right \rfloor\)，于是
\[\begin{aligned}\sum_{i=1}^{N}\sum_{j=1}^{M}d(ij)&=\sum_{d=1}^{N} \mu(d) \sum_{i=1}^{\left \lfloor \frac {N} {d} \right \rfloor} \left \lfloor\frac{\left \lfloor\frac{N}{d}\right\rfloor}{i}\right\rfloor \sum_{j=1}^{\left \lfloor \frac {M} {d} \right \rfloor} \left \lfloor\frac{\left \lfloor\frac{M}{d}\right\rfloor}{j}\right\rfloor\\&=\sum_{d=1}^{N}\mu(d)g(\left \lfloor\frac{N}{d}\right \rfloor) g(\left \lfloor\frac{M}{d}\right\rfloor)\end{aligned}\]
注意到\(g\)是\(d\)的前缀和，而\(d\)是积性函数，可以线性筛出\(d\)之后预处理出\(g\)。

之后用分块加速计算就可以了。

约数个数和：枚举gcd的值k。利用mobius变换，统计的结果是mu*一个可以预处理出来的值（关于n/k与m/k的）。然后再发现对于连续的若干个k，这样的结果是相同的。所以只要把k的考虑一块一块来，似乎蛮简单的。

AC代码：
```c++
测试数据 #0: Accepted, time = 31 ms, mem = 1584 KiB, score = 10
测试数据 #1: Accepted, time = 46 ms, mem = 1588 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1588 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1588 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 1584 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 1584 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 1588 KiB, score = 10
测试数据 #7: Accepted, time = 593 ms, mem = 1588 KiB, score = 10
测试数据 #8: Accepted, time = 546 ms, mem = 1588 KiB, score = 10
测试数据 #9: Accepted, time = 562 ms, mem = 1584 KiB, score = 10
Accepted, time = 1778 ms, mem = 1588 KiB, score = 100

#include <iostream>
#include <cstring>
#include <cstdio>
#define LL long long
#define maxn 50001
using namespace std;
int tot,prime[30001],mu[maxn],c[maxn];
LL d[maxn],Ans[101][101];
bool isprime[maxn];

int gcd(int a,int b) {
return b?gcd(b,a%b):a;
}

void genPrime(int n) {
memset(isprime,1,sizeof isprime);
mu[1] = d[1] = c[1] = 1;
for (int i=2;i<=n;++i) {
if (isprime[i]) {
prime[tot++] = i;
mu[i] = -1;
c[i] = 1;
d[i] = 2;
}
for (int j=0;j<tot && i*prime[j]<=n;++j) {
isprime[i*prime[j]] = 0;
if (i%prime[j] == 0) {
d[i*prime[j]] = d[i]/(c[i] + 1)*(c[i] + 2);
c[i*prime[j]] = c[i] + 1;
break;
}
mu[i*prime[j]] = -mu[i];
d[i*prime[j]] = d[i] * d[prime[j]];
c[i*prime[j]] = 1;
}
}
for (int i=1;i<=n;++i) mu[i] += mu[i-1];
for (int i=1;i<=n;++i) d[i] += d[i-1];
}

inline int read() {
int x = 0;
char ch = getchar();
while (!isdigit(ch)) ch = getchar();
while (isdigit(ch)) x = x * 10 + ch - 48,ch = getchar();
return x;
}

char a[18];

inline void print(LL x) {
a[0] = 0;
while (x) a[++a[0]] = x%10,x/=10;
for (;a[0];--a[0])
putchar(a[a[0]]+48);
putchar('\n');
}

int main() {
genPrime(50000);
int t = read();
while (t--) {
int n = read(),m = read();
if (n <= 100 && m <= 100) {
if (Ans[n][m]) {
print(Ans[n][m]);
continue;
}
}
if (n > m) swap(n,m);
LL ans = 0;
for (int i=1,nex;i<=n;i=nex+1) {
nex = min(n/(n/i),m/(m/i));
ans += (mu[nex] - mu[i-1]) * d[n/i] * d[m/i];
}
if (n<=100 && m<=100) Ans[n][m] = Ans[m][n] = ans;
print(ans);
}
return 0;
}
```

*Doc你太深奥了，看不懂
*能贴部分类似mobius的代码吗
*大概K要怎么计算
*谢谢