[SDOI2015]约数个数和

如题，设$d(x)$表示$x$的约数个数，求$\sum_{i = 1}^N \sum_{j = 1}^Md(i \times j)$
首先要知道约数个数的一种表示方法：$d(i,j) = \sum_{x|i} \sum_{y_j}[gcd(x,y) == 1]$
然后题目所求就变成了

$$\sum_{i = 1}^N \sum_{j = 1}^M \sum_{k | i} \sum_{l | j}[gcd(k,l) == 1]$$

化简，改变量之后式子变为

$$\sum_{i = }^N \sum_{j = 1}^M(gcd(i,j) == 1)(\frac Mi)(\frac Mj)$$

考虑莫比乌斯反演,设

$$f(X) = \sum_{i = }^N \sum_{j = 1}^M(gcd(i,j) == x)(\frac Ni)(\frac Mj)$$ $$F(x) = \sum_{x|n}f(n)$$ $$→ F(x) = \sum_{i = }^N \sum_{j = 1}^{N / x}(x|gcd())(\frac Ni)(\frac Mj)$$ $$→ F(x) = \sum_{i = }^N \sum_{j = 1}^{M / x}(\frac {N}{ix})(\frac {M}{jx})$$

考虑优化算法时间复杂度，可以预处理出$\sum_{i = 1}^N(\frac Ni)$和$\sum_{j = 1}^M (\frac Mj)$，连带着莫比乌斯函数可以直接O(N)预处理。

inline void Init() {
	U[1] = F[1] = 1 ;
	for (int i = 2 ; i <= MAXN ; i ++) V[i] = true ;
	for (int i = 2 ; i <= MAXN ; i ++) {
		if (V[i]) U[i] = - 1, P[++ Tot] = i, F[i] = 2, G[i] = 1 ;
		for (int j = 1 ; j <= Tot && i * P[j] < MAXN ; j ++) {
			V[i * P[j]] = false ;
			if (i % P[j] == 0) {
				U[i * P[j]] = 0 ;
				F[i * P[j]] = F[i] / (G[i] + 1) * (G[i] + 2) ;
				G[i * P[j]] = G[i] + 1 ;
				break ;
			}	else 
			U[i * P[j]] = - U[i], F[i * P[j]] = (F[i] << 1), G[i * P[j]] = 1 ;
		}
	}
	for (int i = 1 ; i <= MAXN ; i ++) 
		S[i] = S[i - 1] + U[i], Sum[i] = Sum[i - 1] + F[i] ;
}

问题答案化简为$f(1)$。反演后得到$f(1) = \sum{x = 1}^N \mu (x) F(x)$

$$= \sum_{x = 1}^N \mu(x) \sum_{i = 1}^{N/x} \sum _{j = 1}^{M / x} (\frac Ni) (\frac Mj)$$

进行数论分块就可以了，总体时间复杂度$O(T\sqrt N)$，其中T为数据组数。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std ;

typedef long long LL ;
const int MAXN = 50010 ;
const int MAXM = 50010 ;

int N, M, U[MAXN], P[MAXN], Tot ;
int S[MAXN], Sum[MAXN], F[MAXN], G[MAXN] ;
bool V[MAXN] ;	long long Ans ;

inline int Read() {
	int X = 0, F = 1 ; char ch = getchar() ;
	while (ch > '9' || ch < '0') F = (ch == '-' ? - 1 : 1), ch = getchar() ;
	while (ch >= '0' && ch <= '9') X=(X<<1)+(X<<3)+(ch^48), ch = getchar() ;
	return X * F ;
}

inline void Init() {
	U[1] = F[1] = 1 ;
	for (int i = 2 ; i <= MAXN ; i ++) V[i] = true ;
	for (int i = 2 ; i <= MAXN ; i ++) {
		if (V[i]) U[i] = - 1, P[++ Tot] = i, F[i] = 2, G[i] = 1 ;
		for (int j = 1 ; j <= Tot && i * P[j] < MAXN ; j ++) {
			V[i * P[j]] = false ;
			if (i % P[j] == 0) {
				U[i * P[j]] = 0 ;
				F[i * P[j]] = F[i] / (G[i] + 1) * (G[i] + 2) ;
				G[i * P[j]] = G[i] + 1 ;
				break ;
			}	else 
			U[i * P[j]] = - U[i], F[i * P[j]] = (F[i] << 1), G[i * P[j]] = 1 ;
		}
	}
	for (int i = 1 ; i <= MAXN ; i ++) 
		S[i] = S[i - 1] + U[i], Sum[i] = Sum[i - 1] + F[i] ;
}

int main() {
	int T = Read() ; Init () ;
	while (T --) {	Ans = 0 ;
		N = Read() ; M = Read() ;
		for (int l = 1, r ; l <= min(N, M) ; l = r + 1) {
			r = min(N / (N / l), M / (M / l)) ;
			Ans += 1ll * (S[r] - S[l - 1]) * Sum[N / l] * Sum[M / l] ;
		}	printf("%lld\n", Ans) ;
	}
}