思路

做这题先要知道一个性质，

\[ d_{ij}=\sum_{x|i}\sum_{y|j}[(x,y)=1] \]

然后上莫比乌斯反演颓柿子就好了

\[ \begin{align}&\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}[(x,y)=1]\\=&\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}\sum_{d|(x,y)}\mu(d)\\=&\sum_{i=1}^n\sum_{j=1}^m\sum_d^{min(n,m)}\mu(d)\sum_{x=1}^{\lfloor\frac{i}{d}\rfloor}\sum_{y=1}^{\lfloor\frac{j}{d}\rfloor}1\\=&\sum_d^{min(n,m)}\mu(d)\sum_{i=1}^n\sum_{x=1}^{\lfloor\frac{i}{d}\rfloor}\sum_{j=1}^m\sum_{y=1}^{\lfloor\frac{j}{d}\rfloor}1\\=&\sum_d^{min(n,m)}\mu(d)\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{n}{xd}\rfloor\sum_{y=1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{m}{dy}\rfloor\\=&\sum_d^{min(n,m)}\mu(d)\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{\lfloor \frac{n}{d}\rfloor}{x}\rfloor\sum_{y=1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{\lfloor \frac{m}{d} \rfloor}{y}\rfloor\end{align}\\ \]

后面的部分，预处理一个\(\sum_{i=1}^n \lfloor \frac{n}{i} \rfloor\)就好了，前面上一个整除分块

代码

#include 
    
     #include 
     
      #include 
      
       using namespace std;int isprime[50010],mu[50010],cnt,iprime[50010],n,m,t;long long sum[50010];void prime(int n){    mu[1]=1;    isprime[1]=true;    for(int i=2;i<=n;i++){        if(!isprime[i]){            iprime[++cnt]=i;            mu[i]=-1;        }        for(int j=1;j<=cnt&&iprime[j]*i<=n;j++){            isprime[i*iprime[j]]=true;            mu[i*iprime[j]]=-mu[i];            if(i%iprime[j]==0){                mu[i*iprime[j]]=0;                break;            }        }    }    for(int i=1;i<=n;i++)        mu[i]+=mu[i-1];}void pre(int n){    for(int i=1;i<=n;i++){        long long ans=0;        for(int l=1,r;l<=i;l=r+1){            r=i/(i/l);            ans=ans+1LL*(r-l+1)*(i/l);        }        sum[i]=ans;    }}int main(){    scanf("%d",&t);    prime(50000);    pre(50000);    // printf("ok\n");    while(t--){        scanf("%d %d",&n,&m);        long long ans=0;        for(int l=1,r;l<=min(n,m);l=r+1){            r=min(n/(n/l),m/(m/l));            // printf("l=%d\n",l);            ans=ans+1LL*(mu[r]-mu[l-1])*sum[n/l]*sum[m/l];        }        printf("%lld\n",ans);    }    return 0;}