前置芝士
关于这个题，你必须知道一个这样奇奇怪怪的式子啊QAQ
[d(i*j)= sum_{x|i} sum_{y|j}[gcd(x,y)=1]
]
留坑，先感性理解：后面那个gcd是为了去重。
UPD：
正文
根据前一部分，我们所要推倒的式子就变成了
[ans=sum_{i=1}^{n}sum_{j=1}^{m}sum_{x|i}sum_{y|j}left [ gcd(x,y)=1
ight ]
]
我们可以改变一下枚举顺序，原来是枚举原数，现在我们改为枚举约数，再利用数学性质将其倍数全部筛掉，式子即变成
[ans=sum_{i=1}^{n}sum_{j=1}^{m}left lfloor frac{n}{i}
ight
floorleft lfloor frac{m}{j}
ight
floorleft [ gcd(i,j)=1
ight ]
]
于是，我们可以把里面的那个东西稍稍的替换一下
[ans=sum_{i=1}^{n}sum_{j=1}^{m}left lfloor frac{n}{i}
ight
floorleft lfloor frac{m}{j}
ight
floorsum_{d|gcd(i,j)}mu (d)
]
根据莫比乌斯函数的性质，这两个东西显然是等价的。
然后我们可以在和式枚举时就将gcd消掉,同时将d调整到和式最外层
然后整个式子就变成
[ans=sum_{d=1}^{min(n,m)}mu (d)sum_{x=1}^{left lfloor frac{n}{x}
ight
floor}left lfloor frac{n}{dx}
ight
floorsum_{y=1}^{left lfloor frac{m}{y}
ight
floor}left lfloor frac{m}{dy}
ight
floor
]
唯一的难点是，$sum_{x=1}^{left lfloor frac{n}{x} ight floor}left lfloor frac{n}{dx} ight floor $
将(n/x)，换成一个变量，就会发现，这东西也是可以分块的！！！
然后就可以愉快的整除分块了
贴代码
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=5e4+10;
int miu[maxn],prime[maxn],t;
bool vis[maxn];
ll g[maxn];
void get_g()
{
for(int i=1;i<=maxn;++i)
{
int l,r;
for(l=1;l<=i;l=r+1)
{
r=i/(i/l);
g[i]+=(i/l)*(r-l+1);
}
}
}//同样分块处理
void mobius()
{
miu[1]=1;
for(int i=2;i<=maxn;i++)
{
if(vis[i]==0)
miu[i]=-1,++t,prime[t]=i;
for(int j=1;j<=t&&i*prime[j]<=maxn;++j)
{
vis[i*prime[j]]=1;
if(!(i%prime[j])) break;
else miu[i*prime[j]]-=miu[i];
}
}
for(int i=1;i<=maxn;++i)
miu[i]+=miu[i-1];
}
int main()
{
get_g();
mobius();
int t;
int n,m;
scanf("%d",&t);
for(int _=1;_<=t;++_)
{
ll ans=0;
scanf("%d%d",&n,&m);
int tmp=min(n,m);
long long l,r;
for(l=1;l<=tmp;l=r+1)
{
r=min(n/(n/l),m/(m/l));
ans+=(miu[r]-miu[l-1])*g[n/l]*g[m/l];
}
printf("%lld
",ans);
}
}