[国家集训队]Crash的数字表格

Link
如题，给定$N$和$M$，求

$$\sum_{i = 1} ^ N \sum_{j = 1}^ M lcm(i, j)$$

有人说这道题是BZOJ上面的JZPTAB，但其实不是，JZBTAB虽然具体问题和改题是一样的，但是那道题是多组询问，比这道题还要难一些。
首先我们知道$lcm(i,j) = \frac{i \times j}{gcd(i,j)}$，那么题目转化为

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

然后我们枚举最大公约数，式子转化为

$$\sum_{d = 1}^{min(N,M)} \sum_{i = 1} ^ N \sum_{j = 1}^ M \frac{i \times j}{d} [gcd(i,j) == d]$$

提出d,式子变成

$$\sum_{d = 1}^{min(N,M)} d \sum_{i = 1}^{N / d} \sum_{j = 1} ^ {M / d}[gcd(i, j) == 1] \times ij$$

并且我们知道

$$\sum_{d|N}\mu (d) = [N == 1]$$

直接带入上面的式子可以得到

$$\sum_{d = 1}^{min(N,M)} d \sum_{i = 1}^{N / d} \sum_{j = 1} ^ {M / d} \sum_{x|gcd(i,j)} \mu (x) \times ij$$

保留前缀和$S[i]$，优先枚举$x$。

$$\sum _{d = 1} ^ N d \sum_{x = 1}^{n / d} x ^ 2 μ (x) S(\frac {N}{dx}) S(\frac {M}{dx})$$

优先枚举$S$

$$\sum_{dx = 1}^{N} S(\frac{N}{dx} S(\frac{M}{dx})dx \sum_{e|dx}e \mu(dx))$$

对于其中的$f(dx) = dx \sum_{e|dx}e \mu(dx)$可以线性筛，有式子

$$f(dxp) = f(dx)f(p)$$

之后的式子可以整除分块。

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

using namespace std ;

typedef long long LL ;
const int MAXN = 10000010 ;
const int MAXM = 10000010 ;
const int Mod = 20101009 ;

int N, M, F[MAXN], P[MAXN], Tot ;
bool V[MAXN] ;	int Sum[MAXN], 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 int MOD (int Now) {
	if (Now >= Mod) return Now - Mod ;
	else return Now ;
}

inline void Init() {
	F[1] = 1 ;
	for (int i = 2 ; i <= min(N, M) ; i ++) {
		if (! V[i]) {
			P[++ Tot] = i, F[i] = MOD (Mod + 1 - i) ;
		}
			
		for (int j = 1 ; j <= Tot && i * P[j] <= min(N, M) ; j ++) {
			V[i * P[j]] = true ;
			if (i % P[j]) F[i * P[j]] = 1LL * F[i] * F[P[j]] % Mod ;
			else {
				F[i * P[j]] = F[i] ;
				break ;
			}
		}
	}

	for (int i = 1 ; i <= min(N, M) ; i ++)
		F[i] = MOD(F[i - 1] + 1ll * F[i] * i % Mod) ;
	for (int i = 1 ; i <= max(N, M) ; i ++)
		Sum[i] = MOD(Sum[i - 1] + i) ;
}

int main() {
	N = Read() ; M = Read() ; Init() ; Ans = 0 ;
	for (int l = 1, r ; l <= min(N, M) ; l = r + 1) {
		r = min(N / (N / l), M / (M / l)) ;
		int Ans2 = MOD(F[r] - F[l - 1] + Mod) ;
		Ans = MOD(Ans + 1LL * Ans2 * Sum[N / l] % Mod * Sum[M / l] % Mod) ;
	}	
	printf("%d", Ans % Mod) ;
	return 0 ;
}

这道题的式子确实难推，但是时间复杂度化简到$O(N)$左右也就可以了，据说BZOJ上面的题目是真正的JZPTAB是多组数据，时间复杂度要推倒$O(\sqrt N)$才行。至于那种级别的题目，即使没有眼见为实，笔者也是有做不了的自知之明的…如果有想要了解的朋友还请另寻高就吧。