题目大意

设 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=1∑n​j=1∑m​d(ij)

题解

首先有一个奇妙的结论：
d ( i j ) = ∑ x ∣ i ∑ y ∣ i [ g c d ( x , y ) = = 1 ] d(ij)=\sum_{x|i}\sum_{y|i}[gcd(x,y)==1] d(ij)=x∣i∑​y∣i∑​[gcd(x,y)==1]
证明如下：
根据定义， d ( i j ) = ∑ p ∣ i j 1 d(ij)=\sum_{p|ij}1 d(ij)=p∣ij∑​1
我们尝试把 p p p 拆开，设 x y = p xy=p xy=p ，那我们若我们枚举 x , y x,y x,y 则因为 x ∣ i x|i x∣i 且 y ∣ j y|j y∣j，则 x y ∣ i j xy|ij xy∣ij ，但发现会有重复，而如果我们假设 g c d ( x , y ) = 1 gcd(x,y)=1 gcd(x,y)=1 ，则有
d ( i j ) = ∑ x ∣ i ∑ y ∣ j [ g c d ( 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]
将上式代入原式得：
∑ i = 1 n ∑ j = 1 m ∑ x ∣ i ∑ y ∣ j [ g c d ( x , y ) = = 1 ] \sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}[gcd(x,y)==1] i=1∑n​j=1∑m​x∣i∑​y∣j∑​[gcd(x,y)==1]
我们尝试改变求和顺序，得：
∑ x = 1 n ∑ y = 1 m [ g c d ( x , y ) = = 1 ] ⋅ ⌊ n x ⌋ ⋅ ⌊ m y ⌋ \sum_{x=1}^n\sum_{y=1}^m[gcd(x,y)==1]\cdot\lfloor\frac{n}{x}\rfloor\cdot\lfloor\frac{m}{y}\rfloor x=1∑n​y=1∑m​[gcd(x,y)==1]⋅⌊xn​⌋⋅⌊ym​⌋
根据莫比乌斯函数的性质 ∑ d ∣ n μ ( d ) = [ n = = 1 ] \sum_{d|n}\mu(d)=[n==1] ∑d∣n​μ(d)=[n==1] ，则
∑ x = 1 n ∑ y = 1 m ∑ d ∣ g c d ( x , y ) μ ( d ) ⋅ ⌊ n x ⌋ ⋅ ⌊ m y ⌋ \sum_{x=1}^n\sum_{y=1}^m\sum_{d|gcd(x,y)}\mu(d)\cdot\lfloor\frac{n}{x}\rfloor\cdot\lfloor\frac{m}{y}\rfloor x=1∑n​y=1∑m​d∣gcd(x,y)∑​μ(d)⋅⌊xn​⌋⋅⌊ym​⌋
= ∑ x = 1 n ∑ y = 1 m ⌊ n x ⌋ ⋅ ⌊ m y ⌋ ∑ d ∣ g c d ( x , y ) μ ( d ) =\sum_{x=1}^n\sum_{y=1}^m\lfloor\frac{n}{x}\rfloor\cdot\lfloor\frac{m}{y}\rfloor\sum_{d|gcd(x,y)}\mu(d) =x=1∑n​y=1∑m​⌊xn​⌋⋅⌊ym​⌋d∣gcd(x,y)∑​μ(d)
继续尝试改变求和顺序，考虑枚举 d d d ，则
∑ d = 1 m i n ( n , m ) μ ( d ) ∑ d ∣ x ⌊ n x ⌋ ∑ d ∣ y ⌊ m y ⌋ \sum_{d=1}^{min(n,m)}\mu(d)\sum_{d|x}\lfloor\frac{n}{x}\rfloor\sum_{d|y}\lfloor\frac{m}{y}\rfloor d=1∑min(n,m)​μ(d)d∣x∑​⌊xn​⌋d∣y∑​⌊ym​⌋
依旧不好维护，我们考虑枚举 x d , y d \frac{x}{d},\frac{y}{d} dx​,dy​ ，则
∑ d = 1 m i n ( n , m ) μ ( d ) ∑ x = 1 ⌊ n d ⌋ ⌊ ⌊ n d ⌋ x ⌋ ∑ y = 1 ⌊ m d ⌋ ⌊ ⌊ m d ⌋ y ⌋ \sum_{d=1}^{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 d=1∑min(n,m)​μ(d)x=1∑⌊dn​⌋​⌊x⌊dn​⌋​⌋y=1∑⌊dm​⌋​⌊y⌊dm​⌋​⌋
设 f ( n ) = ∑ i = 1 n ⌊ n i ⌋ f(n)=\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor f(n)=∑i=1n​⌊in​⌋ ，则
∑ d = 1 m i n ( n , m ) μ ( d ) ⋅ f ( ⌊ n d ⌋ ) ⋅ f ( ⌊ m d ⌋ ) \sum_{d=1}^{min(n,m)}\mu(d)\cdot f(\lfloor\frac{n}{d}\rfloor)\cdot f(\lfloor\frac{m}{d}\rfloor) d=1∑min(n,m)​μ(d)⋅f(⌊dn​⌋)⋅f(⌊dm​⌋)
函数 f f f 可以用 O ( n n ) O(n\sqrt n) O(nn ​) 的时间复杂度预处理，然后用数论分块便可解决此题。

Code

#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
const int N=50005;
int n,m,cnt;
bool bz[N];
int prime[N];
ll mu[N],sum[N],f[N];
void work(){
	mu[1]=1;
	for (int i=2;i<=N-5;++i){
		if (!bz[i]){
			bz[i]=1;
			prime[++cnt]=i;
			mu[i]=-1;
		}
		for (int j=1;j<=cnt&&i*prime[j]<=N-5;++j){
			bz[i*prime[j]]=1;
			if (i%prime[j]==0) break;
			mu[i*prime[j]]=-mu[i];
		}
	}
	for (int i=1;i<=N-5;++i){
		sum[i]=sum[i-1]+mu[i];
		for (int l=1,r=0;l<=i;l=r+1){
			r=i/(i/l);
			f[i]+=(ll)(r-l+1)*(ll)(i/l);
		}
	}
	return;
}
int main(){
	work();
	int Q;
	scanf("%d",&Q);
	while (Q--){
		scanf("%d%d",&n,&m);
		ll ans=0;
		for (int l=1,r=0;l<=min(n,m);l=r+1){
			r=min(n/(n/l),m/(m/l));
			ans+=(sum[r]-sum[l-1])*f[n/l]*f[m/l];
		}
		printf("%lld\n",ans);
	}
	return 0;
}