P1829 [CTT2010]Crash 的数字表格 解题笔记

原文创建时间：2021-02-25 21:37:19

题目链接

P1829

题意简述

给定 $n,m$，求
$$\displaystyle \sum_{i=1}^n\sum_{j=1}^m\mathrm{lcm}(i,j)$$

答案对 $20101009$ 取模。

解

不妨令 $n \leq m$。

$\displaystyle \ \ \ \ \sum_{i=1}^n\sum_{j=1}^m\mathrm{lcm}(i,j)$

$\displaystyle = \sum_{i=1}^n\sum_{j=1}^m\frac{ij}{\gcd(i,j)}$

$\displaystyle = \sum_{d=1}^n\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}ijd[i\perp j]$

$\displaystyle = \sum_{d=1}^nd\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}i\sum_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}j[i\perp j]$

$\displaystyle = \sum_{d=1}^nd\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}i\sum_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}j\sum_{k|\gcd(i,j)}\mu(k)$

$\displaystyle = \sum_{d=1}^nd\sum_{k=1}^{\left\lfloor\frac{n}{d}\right\rfloor}k^2\mu(k)\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}i[k|i]\sum_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}j[k|j]$

$\displaystyle = \sum_{d=1}^nd\sum_{k=1}^{\left\lfloor\frac{n}{d}\right\rfloor}k^2\mu(k)f\left(\left\lfloor\frac{n}{dk}\right\rfloor\right)f\left(\left\lfloor\frac{m}{dk}\right\rfloor\right)$

此处 $f$ 即熟知的等差数列求和：
$$\displaystyle f(n) = \frac{n(n+1)}{2}$$

接下来，令 $t = dk$：

$\displaystyle \ \ \ \ \sum_{t=1}^n\sum_{k|t}\frac{t}{k}k^2\mu(k)f\left(\left\lfloor\frac{n}{t}\right\rfloor\right)f\left(\left\lfloor\frac{m}{t}\right\rfloor\right)$

$\displaystyle = \sum_{t=1}^nf\left(\left\lfloor\frac{n}{t}\right\rfloor\right)f\left(\left\lfloor\frac{m}{t}\right\rfloor\right)\sum_{k|t}\frac{t}{k}k^2\mu(k)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (*)$

下面有两种推导。

推导一

考察第二层枚举，可以表示成卷积的形式：

设
$$g(n) = n^2 \cdot \mu(n)$$

则
$$\displaystyle \sum_{k|t}\frac{t}{k}k^2\mu(k) = (g \ast \mathrm{Id})(t)$$

回到原式：

$\displaystyle \ \ \ \ \sum_{t=1}^nf\left(\left\lfloor\frac{n}{t}\right\rfloor\right)f\left(\left\lfloor\frac{m}{t}\right\rfloor\right)\sum_{k|t}\frac{t}{k}k^2\mu(k)$

$\displaystyle = \sum_{t=1}^n(g \ast \mathrm{Id})(t)f\left(\left\lfloor\frac{n}{t}\right\rfloor\right)f\left(\left\lfloor\frac{m}{t}\right\rfloor\right)$

考虑 $h =(g \ast \mathrm{Id})$ 的求法。

对于质数 $p$，易见
$$\displaystyle h\left(p^\alpha\right) = g(1)p^\alpha + g( p )p^{\alpha - 1} = p^\alpha(1 - p)$$

故线性筛并前缀和。

时间复杂度：$\displaystyle \mathrm{O} \left(n+\sqrt{n}\right)$

推导一代码

#include<bits/stdc++.h>
#define REG register

using namespace std;

namespace ACAH
{
	typedef long long ll;
	
	const int maxn = 1e7 + 7;
	const ll Mod = 20101009;
	const ll inv = 10050505;
	
	int N, M;
	ll ans;
	int pr[maxn], pc;
	bool ip[maxn];
	ll h[maxn];
	
	template<typename T> inline void qread(T &x)
	{
		x = 0; REG char ch = getchar();
		while(!isdigit(ch)) ch = getchar();
		while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	}
	
	inline ll Min(ll a, ll b) {return a < b ? a : b;}
	inline ll Sum(ll a, ll b) {return (a + b) * (b - a + 1) % Mod * inv % Mod;}
	
	void linear_sieve()
	{
		h[1] = 1;
		for(REG int i = 2; i <= N; i++) {
			if(!ip[i]) pr[++pc] = i, h[i] = 1ll * i * (1ll - i) % Mod;
			for(REG int j = 1; j <= pc && 1ll * i * pr[j] <= N; j++) {
				REG int c = i * pr[j]; ip[c] = true;
				if(i % pr[j]) h[c] = h[i] * pr[j] % Mod * (1ll - pr[j]) % Mod;
				else {h[c] = h[i] * pr[j] % Mod, h[c] %= Mod; break;}
			}
		}
		for(REG int i = 2; i <= N; i++) h[i] = (h[i] + h[i - 1]) % Mod;
	}
	
	int work()
	{
		qread(N), qread(M); if(N > M) swap(N, M);
		linear_sieve();
		for(REG ll l = 1, r; l <= N; l = r + 1) {
			r = Min(N / (N / l), M / (M / l));
			ans += Sum(1, N / l) * Sum(1, M / l) % Mod * (h[r] - h[l - 1]) % Mod;
			ans %= Mod;
		}
		printf("%lld", (ans + Mod) % Mod);
		return 0;
	}
}

int main() {return ACAH::work();}

---

推导二

先把 $\displaystyle \frac{t}{k}k^2\mu(k)$ 约分成 $tk\mu(k)$。

现在 $t$ 已经与 $k$ 枚举无关，将其提前：

$\displaystyle \ \ \ \ \sum_{t=1}^nf\left(\left\lfloor\frac{n}{t}\right\rfloor\right)f\left(\left\lfloor\frac{m}{t}\right\rfloor\right)\sum_{k|t}tk\mu(k)$

$\displaystyle = \sum_{t=1}^nf\left(\left\lfloor\frac{n}{t}\right\rfloor\right)f\left(\left\lfloor\frac{m}{t}\right\rfloor\right)t\sum_{k|t}k\mu(k)$

此时第二层枚举也可以表示成卷积的形式。类似地设 $g(n) = n\mu(n)$，则有
$$\displaystyle \sum_{k|t}k\mu(k) = (1 \ast g)(t)$$

设 $h = 1 \ast g$。

易见对于质数 $p$ 有
$$h\left(p^\alpha\right) = g(1) + g( p ) = 1 - p$$

故线性筛处理。

注意在数论分块时，$f$ 的值在同一块中是一样的，但是 $t$ 和 $h(t)$ 是连续变化的，故前缀和时宜将 $t \cdot h(t)$ 整体作前缀和处理。可以发现，这样做的话，最终处理出的结果与推导一实际上没有区别。

时间复杂度：$\displaystyle \mathrm{O} \left(n+\sqrt{n}\right)$

推导二代码

#include<bits/stdc++.h>
#define REG register

using namespace std;

namespace ACAH
{
	typedef long long ll;
	
	const int maxn = 1e7 + 7;
	const ll Mod = 20101009;
	const ll inv = 10050505;
	
	int N, M;
	ll ans;
	int pr[maxn], pc;
	bool ip[maxn];
	ll h[maxn];
	
	template<typename T> inline void qread(T &x)
	{
		x = 0; REG char ch = getchar();
		while(!isdigit(ch)) ch = getchar();
		while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	}
	
	inline ll Min(ll a, ll b) {return a < b ? a : b;}
	inline ll Sum(ll a, ll b) {return (a + b) * (b - a + 1) % Mod * inv % Mod;}
	
	void linear_sieve()
	{
		h[1] = 1;
		for(REG int i = 2; i <= N; i++) {
			if(!ip[i]) pr[++pc] = i, h[i] = (1ll - i) % Mod;
			for(REG int j = 1; j <= pc && 1ll * i * pr[j] <= N; j++) {
				REG int c = i * pr[j]; ip[c] = true;
				if(i % pr[j]) h[c] = h[i] * (1ll - pr[j]) % Mod;
				else {h[c] = h[i]; break;}
			}
		}
		for(REG int i = 2; i <= N; i++) h[i] = (h[i] * i % Mod + h[i - 1]) % Mod;
	}
	
	int work()
	{
		qread(N), qread(M); if(N > M) swap(N, M);
		linear_sieve();
		for(REG ll l = 1, r; l <= N; l = r + 1) {
			r = Min(N / (N / l), M / (M / l));
			ans += Sum(1, N / l) % Mod * Sum(1, M / l) % Mod * (h[r] - h[l - 1]) % Mod;
			ans %= Mod;
		}
		printf("%lld", (ans + Mod) % Mod);
		return 0;
	}
}

int main() {return ACAH::work();}

---

后记

关于咕咕咕这道题

这道题好像已经在洛谷的推荐列表里面好一阵子了，Spring Camp 课程和学长讲课也都将其留作了作业。在咕咕咕了一阵子之后开始看这道题。

从开始看到通过题目、写完这篇笔记，总共跨度 24 小时，中间咕了数次终于完成。

2021 年 2 月 28 日又修订了一点，并补充了第二种推导思路。

关于解题过程中的一些注意

在推导到 $(*)$ 之后，如果将 $\displaystyle \frac{t}{k}k^2\mu(k)$ 直接化简成为 $tk\mu(k)$，千万不要像我一样以为这是 $\mu \ast \mathrm{Id} = \varphi$，果断在最后一步推错。

花絮 / 警示

Sum 函数求等差数列之和，我居然一开始在取模后使用了除法！交上去 WA 30 分让我一度以为是 long long 炸了或者是线性筛出了问题……

模意义下，一定要用逆元！！！