设 d ( x ) d(x) d(x) 为 x x x 的约数个数，给定 n , m n,m n,m，求 ∑ i = 1 n ∑ j = 1 m d ( i j ) \sum_{i=1}^n\sum_{j=1}^md(ij) ∑i=1n​∑j=1m​d(ij)

首先看 d ( i j ) = ∑ x ∣ i ∑ y ∣ j [ gcd ⁡ ( x , y ) = 1 ] d(ij)=\sum_{x|i}\sum_{y|j} [\gcd(x,y)=1] d(ij)=∑x∣i​∑y∣j​[gcd(x,y)=1]
然后我们看这个题的 F ( n ) F(n) F(n)和 f ( n ) f(n) f(n)
F ( n ) = ∑ i = 1 N ∑ j = 1 M ∑ x ∣ i ∑ y ∣ j [ n ∣ ( x , y ) ] F(n)=\sum _{i=1}^N\sum_{j=1}^{M}\sum_{x|i}\sum_{y|j}[n|(x,y)] F(n)=i=1∑N​j=1∑M​x∣i∑​y∣j∑​[n∣(x,y)]
交换位置得
∑ x = 1 N ∑ y = 1 M [ N x ] [ M y ] [ n ∣ ( x , y ) ] \sum _{x=1}^N\sum_{y=1}^{M}[\frac{N}{x}][\frac{M}{y}][n|(x,y)] x=1∑N​y=1∑M​[xN​][yM​][n∣(x,y)]
设 x ′ = x n , y ′ = y n x'=\frac{x}{n},y'=\frac{y}{n} x′=nx​,y′=ny​得
∑ x ′ = 1 N n ∑ y ′ = 1 M n [ N x ′ n ] [ M y ′ n ] \sum _{x'=1}^{\frac{N}{n}}\sum_{y'=1}^{\frac{M}{n}}[\frac{N}{x'n}][\frac{M}{y'n}] x′=1∑nN​​y′=1∑nM​​[x′nN​][y′nM​]
然后我们替换一下N和M N ′ = N n N'=\frac{N}{n} N′=nN​ M ′ = M n M'=\frac{M}{n} M′=nM​代入得：
∑ x ′ = 1 N ′ ∑ y ′ = 1 M ′ [ N ′ x ′ ] [ M ′ y ′ ] \sum _{x'=1}^{N'}\sum_{y'=1}^{M'}[\frac{N'}{x'}][\frac{M'}{y'}] x′=1∑N′​y′=1∑M′​[x′N′​][y′M′​]
然后我们整理一下 让 x ′ , y ′ x',y' x′,y′更好表示用 i , j i,j i,j替代：
∑ i = 1 N ′ ∑ j = 1 M ′ [ N ′ i ] [ M ′ j ] \sum _{i=1}^{N'}\sum_{j=1}^{M'}[\frac{N'}{i}][\frac{M'}{j}] i=1∑N′​j=1∑M′​[iN′​][jM′​]
在整理一下把与i有关的放一起，把与j有关的放一起：
∑ i = 1 N ′ [ N ′ i ] ∑ j = 1 M ′ [ M ′ j ] \sum _{i=1}^{N'}[\frac{N'}{i}]\sum_{j=1}^{M'}[\frac{M'}{j}] i=1∑N′​[iN′​]j=1∑M′​[jM′​]
这里我们看到左边右边是同一个函数引入他
h ( n ) = ∑ i = 1 n [ n i ] h(n)=\sum _{i=1}^{n}[\frac{n}{i}] h(n)=i=1∑n​[in​]
然后上面等于
h ( N ′ ) h ( M ′ ) h(N')h(M') h(N′)h(M′)
我们看 h ( n ) = [ n 1 ] + [ n 2 ] + . . . . + [ n n ] h(n)=[\frac{n}{1}]+[\frac{n}{2}]+....+[\frac{n}{n}] h(n)=[1n​]+[2n​]+....+[nn​]用整除分块预处理出来即可

得到 F ( n ) F(n) F(n)
所以看 f ( n ) f(n) f(n)其实我们要求的是 f ( 1 ) f(1) f(1)
f ( 1 ) = ∑ d = 1 N μ ( d ) F ( d ) = ∑ d = 1 N μ h ( N d ) h ( M d ) f(1)=\sum_{d=1}^N\mu(d)F(d)=\sum_{d=1}^N\mu h(\frac{N}{d})h(\frac{M}{d}) f(1)=d=1∑N​μ(d)F(d)=d=1∑N​μh(dN​)h(dM​)
后面这部分 h ( N d ) h ( M d ) h(\frac{N}{d})h(\frac{M}{d}) h(dN​)h(dM​)也用整除分块维护

#include <bits/stdc++.h>

using namespace std;

#define ll long long 

const int maxn=5e4+7;

int cnt;
int prime[maxn],mu[maxn],sum[maxn],h[maxn];
bool isprime[maxn];

void Prime(){
    mu[1]=1;
    for(int i=2;i<maxn;i++){
        if(!isprime[i]) prime[++cnt]=i,mu[i]=-1;
        for(int j= 1;j<=cnt&&i*prime[j]<maxn;j++){
            isprime[i*prime[j]]=1;
            if(i%prime[j]==0) break;
            mu[i*prime[j]]=-mu[i];
        }
    }    
    for(int i=1;i<maxn;i++){
        sum[i]=sum[i-1]+mu[i];
    }

    for(int i=1;i<maxn;i++){
        for(int l=1,r;l<=i;l=r+1){
            r=min(i,i/(i/l));
            h[i] += (r - l + 1) * (i / l);
        }
    }
}


int main(){
    Prime();
    int t;
    scanf("%d",&t);
    while(t--){
        int n,m;
        scanf("%d%d",&n,&m);
        ll ans=0;
        int minn=min(n,m);
        for(int l=1,r;l<=minn;l=r+1){
            r=min(minn,n/(n/l));
            r=min(r,m/(m/l));
            ans+=(ll)(sum[r]-sum[l-1])*h[n/l] * h[m/l];
        }
        cout<<ans<<endl;
    }
    return 0;
}