这题做的历程堪称惊心动魄

刚刚学了莫比乌斯反演的我高高兴兴的和cbx一起反演式子

期间有突破，有停滞，有否定

然后苟蒻的我背着cbx偷偷打开了题解

看到了

我。。。。。。

去你的有个性质啊（当然还是自己知识储备不足）

具体证明
（其实当时主要是想的方向偏了，不然这个定理自己也能想出来）

然后就可以愉快的反演了

 Σ_{（i∈[1，n]）}Σ_{（j∈[1.m]）}d（x,y）

=Σ_(i=1)Σ_(j=1)Σ_(x|i)Σ_(y|j)[gcd（x,y）==1]

=Σ_(i=1)Σ_(j=1)((n/i)*(m/j))Σ_(d|i&&d|j)μ(d)

=Σ_(d=1)μ(d)Σ_(i=1) (n/(d*i)) Σ_(j=1)(m/(d*j))

然后我们观察Σ(n/(d*i))
根据性质 (n/(d*i))==((n/d)/i)
我们发现这个东西可以用数论分块O(sqrt(n))预处理，设为f[i]
则原式= Σ(d=1)(μ(d)f[n/d]*f[m/d])
再用数论分块就好了
复杂度O(n*sqrt(n)+T*sqrt(n))

#include<iostream>
#include<cstdio>
#include<cmath>
#define ll long long
using namespace std;
int mu[50100],p[50010],top;ll tot[50100],f[50100];bool v[50010];
int main(){
    f[1]=1;tot[1]=1;
    for(int i=2;i<=50000;i++){
        if(!v[i]){
            p[++top]=i;
            mu[i]=-1;
        }
        for(int j=1;j<=top&&i*p[j]<=50000;j++){
            if(!(i%p[j])){
                v[i*p[j]]=1;
                break;
            } 
            mu[i*p[j]]=-mu[i];
            v[i*p[j]]=1;
        }
        tot[i]=tot[i-1]+mu[i];
        int x;
        for(int j=1;j<=i;j=x+1){
            x=(i/(i/j));
            f[i]+=(x-j+1)*(i/j);
        }
    }   
    int j,n,m,t;ll ans;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        if(n>m) swap(n,m);ans=0;
        for(int i=1;i<=n;i=j+1){
            j=min((n/(n/i)),(m/(m/i)));
            ans+=(tot[j]-tot[i-1])*f[n/i]*f[m/i];
        }
        printf("%lld\n",ans);
    }
}