Description
设d(x)为x的约数个数，给定N、M，求 
Input
输入文件包含多组测试数据。
第一行，一个整数T，表示测试数据的组数。
接下来的T行，每行两个整数N、M。
Output
T行，每行一个整数，表示你所求的答案。
题解：
有一个小结论：
$d(ij)=\sum_{i|n}\sum_{j|n}[gcd(i,j)==1]$
原式 $= \sum_{i=1}^{n}\sum_{j=1}^{m}d(ij)$
$\Rightarrow\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x|i}\sum_{y|j}[gcd(x,y)==1]$
$\Rightarrow\sum_{x=1}^{n}\sum_{y=1}^{m}[gcd(x,y)==1]\sum_{x|i}\sum_{y|j}$
$\Rightarrow\sum_{x=1}^{n}\sum_{y=1}^{m}\left \lfloor \frac{n}{x}\right \rfloor\left \lfloor \frac{m}{x} \right \rfloor[gcd(x,y)==1]$
$\Rightarrow\sum_{x=1}^{n}\sum_{y=1}^{m}\left \lfloor \frac{n}{x}\right \rfloor\left \lfloor \frac{m}{x} \right \rfloor\sum_{d|x,d|y}\mu(d)$
$\Rightarrow\sum_{d=1}^{n}\mu(d)\sum_{d|x}\left \lfloor \frac{n}{x} \right \rfloor\sum_{d|y}\left \lfloor \frac{m}{y} \right \rfloor$
$\Rightarrow\sum_{d=1}^{n}\mu(d)\sum_{x=1}^{\left \lfloor \frac{n}{d} \right \rfloor}\left \lfloor \frac{n}{xd} \right \rfloor\sum_{y=1}^{\left \lfloor \frac{m}{d} \right \rfloor}\left \lfloor \frac{m}{yd} \right \rfloor$
剩下的交给整除分块计算就好了.
最好提前预处理出来所有的前缀和.
#include<bits/stdc++.h>
#define setIO(s) freopen(s".in","r",stdin)
#define ll long long
#define maxn 100000
#define M 50002
using namespace std;
int cnt;
bool vis[maxn];
int prime[maxn], mu[maxn];
ll sumv[maxn],Ge[maxn];
ll Sum(int n)
{int i,j; ll re=0; for(i=1;i<=n;i=j+1){ j=n/(n/i); re+=(j-i+1)*(n/i); }return re;
}
void linear_shaker()
{int i,j; mu[1]=1; for(i=2;i<=M;++i) {if(!vis[i]) prime[++cnt]=i, mu[i]=-1; for(j=1;j<=cnt&&1ll*i*prime[j]<=M;++j){vis[i*prime[j]]=1; if(i%prime[j]==0) {mu[i*prime[j]]=0; break; }mu[i*prime[j]]=-mu[i]; }}for(i=1;i<=M;++i) sumv[i]=sumv[i-1]+mu[i]; for(i=1;i<=M;++i) {Ge[i]=Sum(i); }
}
int main()
{
// setIO("input"); linear_shaker();int T,n,m,i,j; ll re; scanf("%d",&T); while(T--){scanf("%d%d",&n,&m); if(n>m) swap(n,m); re=0; for(i=1;i<=n;i=j+1){j=min(n/(n/i), m/(m/i)); re+=(sumv[j]-sumv[i-1])*Ge[n/i]*Ge[m/i]; }printf("%lld\n",re); } return 0;
}