题面

设$f(x)$为x的约数个数，给定$N$、$M$，求$\sum_{i=1}^{n} \sum_{j=1}^{m} f(i j)$

思路

有个定理$f(ij)=\sum_{x | i} \sum_{y | j}[g c d(x, y)=1]$。你问我如何推导，我只能告诉你无可奉告——这里纸太小，写不下。

然后大力推导以后数论分块即可，但是要预处理所有$x$的$\sum_{i=1}^{x}\left\lfloor\frac{x}{i}\right\rfloor$，这个$nsqrt(n)$的除法分块就可以轻松解决了，然后线性筛后对于答案做一次除法分块即可。

代码

#include<bits/stdc++.h>
#define Maxn 50000
using namespace std;
long long T,N,M,mu[Maxn<<1],cnt=0,prime[Maxn<<1],sum_mu[Maxn<<1],g[Maxn<<1],r=0,ans=0;
bool is_prime[Maxn<<1];
int main()
{       
	for (long long i=1;i<=Maxn;i++)
	{
		for (long long l=1;l<=i;l=r+1)
		{
			r=i/(i/l);
			g[i]+=(r-l+1)*(i/l);
		}
	}
	mu[1]=1;sum_mu[1]=1;
	for (long long i=2;i<=Maxn;i++)
	{   
		if (!is_prime[i]) prime[++cnt]=i,mu[i]=-1;
		for (long long j=1;j<=cnt&&i*prime[j]<=Maxn;j++)
		{
			is_prime[i*prime[j]]=1;
			mu[i*prime[j]]=-mu[i];
			if (!(i%prime[j])){mu[i*prime[j]]=0;break;}
		}  
		sum_mu[i]=sum_mu[i-1]+mu[i];
	}   
	r=0;
	cin>>T;
	while (T--)
	{
		ans=0;
		cin>>N>>M;
		for (long long l=1;l<=min(N,M);l=r+1)   
		{
			r=min(N/(N/l),M/(M/l));
			ans+=(sum_mu[r]-sum_mu[l-1])*g[N/l]*g[M/l]; 
		}
		cout<<ans<<endl;
	}
	return 0;
}