Nov 21, 2018

Luogu P1829: Crash 的数字表格

题面

给定 n,mn, m，试求：

∑i=1n∑j=1mlcm⁡(i,j) \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} \operatorname{lcm}(i, j)

答案对 2010100920101009 取模。

数据范围：1≤n,m≤1071 \le n,m \le 10^7

题目链接：Luogu P1829: Crash 的数字表格

分析

显然我们需要往莫比乌斯函数的方向考虑。因此，我们要把 lcm⁡(i,j)\operatorname{lcm}(i, j) 换作使用 gcd⁡(i,j)\gcd(i, j) 表示。

为了方便，下文中假设 n≤mn \le m（如果 n>mn > m 那么两者交换一下就好了）。

∑i=1n∑j=1mlcm⁡(i,j)=∑i=1n∑j=1mijgcd⁡(i,j) \begin{aligned} \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} \operatorname{lcm}(i, j) = & \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} \frac{ij}{\gcd(i, j)} \end{aligned}

我们发现 gcd⁡(i,j)\gcd(i, j) 位于分母，这十分不好处理。因此我们在这里介绍一个技巧，令 gcd⁡(i,j)=k\gcd(i, j) = k 并枚举 kk 从而使得 gcd⁡(i,j)\gcd(i, j) 离开分母：

∑i=1n∑j=1mlcm⁡(i,j)=∑i=1n∑j=1m∑k=1nijk[gcd⁡(i.j)=k]=∑k=1min⁡(n,m)∑i=1⌊nk⌋∑j=1⌊mk⌋ijk[gcd⁡(i,j)=1] \begin{aligned} \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} \operatorname{lcm}(i, j) = & \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} \sum\limits_{k = 1}^{n} \frac{ij}{k} [\gcd(i. j) = k] \\ = & \sum\limits_{k = 1}^{\min(n, m)} \sum\limits_{i = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \sum\limits_{j = 1}^{\left\lfloor \frac{m}{k} \right\rfloor} ijk[\gcd(i, j) = 1] \end{aligned}

终于出现了我们最喜闻乐见的 [gcd⁡(i,j)=1][\gcd(i, j) = 1]，我们按套路对其进行变换：

∑i=1n∑j=1mlcm⁡(i,j)=∑k=1n∑i=1⌊nk⌋∑j=1⌊mk⌋ijk∑d∣gcd⁡(i,j)μ(d)=∑k=1n∑i=1⌊nk⌋∑j=1⌊mk⌋ijk∑d=1⌊nk⌋μ(d)[d∣gcd⁡(i,j)]=∑k=1nk∑d=1⌊nk⌋μ(d)∑i=1⌊nk⌋∑j=1⌊mk⌋ij[d∣gcd⁡(i,j)]=∑k=1nk∑d=1⌊nk⌋μ(d)∑i=1⌊nkd⌋∑j=1⌊mkd⌋ijd2[1∣gcd⁡(i,j)]=∑k=1nk∑d=1⌊nk⌋μ(d)d2∑i=1⌊nkd⌋i∑j=1⌊mkd⌋j \begin{aligned} \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} \operatorname{lcm}(i, j) = & \sum\limits_{k = 1}^{n} \sum\limits_{i = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \sum\limits_{j = 1}^{\left\lfloor \frac{m}{k} \right\rfloor} ijk \sum\limits_{d \mid \gcd(i, j)} \mu(d) \\ = & \sum\limits_{k = 1}^{n} \sum\limits_{i = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \sum\limits_{j = 1}^{\left\lfloor \frac{m}{k} \right\rfloor} ijk \sum\limits_{d = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \mu(d) [d \mid \gcd(i, j)] \\ = & \sum\limits_{k = 1}^{n} k \sum\limits_{d = 1}^{\left\lfloor \frac{n}{k} \right\rfloor}\mu(d) \sum\limits_{i = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \sum\limits_{j = 1}^{\left\lfloor \frac{m}{k} \right\rfloor} ij [d \mid \gcd(i, j)] \\ = & \sum\limits_{k = 1}^{n} k \sum\limits_{d = 1}^{\left\lfloor \frac{n}{k} \right\rfloor}\mu(d) \sum\limits_{i = 1}^{\left\lfloor \frac{n}{kd} \right\rfloor} \sum\limits_{j = 1}^{\left\lfloor \frac{m}{kd} \right\rfloor} ijd^2 [1 \mid \gcd(i, j)] \\ = & \sum\limits_{k = 1}^{n}k \sum\limits_{d = 1}^{\left\lfloor \frac{n}{k} \right\rfloor}\mu(d) d^2 \sum\limits_{i = 1}^{\left\lfloor \frac{n}{kd} \right\rfloor}i \sum\limits_{j = 1}^{\left\lfloor \frac{m}{kd} \right\rfloor} j \end{aligned}

我们注意到最后两项实际上都是等差数列求和。我们不妨令 g(i)=∑i=1nig(i) = \sum\limits_{i = 1}^{n} i，那么有：

∑i=1n∑j=1mlcm⁡(i,j)=∑k=1nk∑d=1⌊nk⌋μ(d)d2g(⌊nkd⌋)g(⌊mkd⌋) \begin{aligned} \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} \operatorname{lcm}(i, j) = & \sum\limits_{k = 1}^{n}k \sum\limits_{d = 1}^{\left\lfloor \frac{n}{k} \right\rfloor}\mu(d) d^2 g\left( \left\lfloor \frac{n}{kd} \right\rfloor \right) g\left( \left\lfloor \frac{m}{kd} \right\rfloor \right) \\ \end{aligned}

令 T=kdT = kd，同时我们考虑枚举 TT，则有：

∑i=1n∑j=1mlcm⁡(i,j)=∑k=1nk∑d=1⌊nk⌋μ(d)d2g(⌊nT⌋)g(⌊mT⌋)=∑T=1ng(⌊nT⌋)g(⌊mT⌋)∑d∣Tμ(d)d2Td=∑T=1ng(⌊nT⌋)g(⌊mT⌋)T∑d∣Tdμ(d) \begin{aligned} \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} \operatorname{lcm}(i, j) = & \sum\limits_{k = 1}^{n}k \sum\limits_{d = 1}^{\left\lfloor \frac{n}{k} \right\rfloor}\mu(d) d^2 g\left( \left\lfloor \frac{n}{T} \right\rfloor \right) g\left( \left\lfloor \frac{m}{T} \right\rfloor \right) \\ = & \sum\limits_{T = 1}^{n} g\left( \left\lfloor \frac{n}{T} \right\rfloor \right) g\left( \left\lfloor \frac{m}{T} \right\rfloor \right) \sum\limits_{d \mid T}\mu(d)d^2\frac{T}{d} \\ = & \sum\limits_{T = 1}^{n} g\left( \left\lfloor \frac{n}{T} \right\rfloor \right) g\left( \left\lfloor \frac{m}{T} \right\rfloor \right)T \sum\limits_{d \mid T}d\mu(d) \end{aligned}

不妨令 F(n)=∑d∣ndμ(d)F(n) = \sum\limits_{d \mid n} d\mu(d) 并对 F(n)F(n) 进行研究。

我们发现，当 a⊥ba \perp b 时（当 a,ba, b 互质时）：

F(a)=∑d∣adμ(d)F(b)=∑d∣bdμ(d) \begin{aligned} F(a) = & \sum\limits_{d \mid a} d\mu(d) \\ F(b) = & \sum\limits_{d \mid b} d\mu(d) \\ \end{aligned}

我们不难发现，由 a⊥ba \perp b，故 aa 和 bb 不存在公共因子，因此 i∣a, j∣b⇔ij∣abi \mid a, \ j \mid b \Leftrightarrow ij \mid ab。又由于 μ(n)\mu(n) 本身又是积性函数，所以有 μ(ab)=μ(a)⋅μ(b)\mu(ab) = \mu(a) \cdot \mu(b)。由此：

F(a)⋅F(b)=∑i∣aiμ(i)∑j∣bjμ(j)=∑ij∣abij⋅μ(ij)=∑k∣abkμ(k)=F(ab) \begin{aligned} F(a) \cdot F(b) = & \sum\limits_{i \mid a}i\mu(i)\sum\limits_{j \mid b}j\mu(j) \\ = & \sum\limits_{ij \mid ab}ij \cdot \mu(ij) \\ = & \sum\limits_{k \mid ab}k\mu(k) \\ = & F(ab) \end{aligned}

我们发现 F(n)F(n) 也是个积性函数！既然是积性函数…… 那么一定可以线性筛：

  1. F(1)=1F(1) = 1；
  2. 若 aa 是质数，F(a)=1−aF(a) = 1 - a；
  3. 若 a⊥ba \perp b，F(ab)=F(a)⋅F(b)F(ab) = F(a) \cdot F(b)；

由此一来，我们就可以 O(N)\mathcal{O}(N) 初始化（线性筛 F(n)F(n)），并借助整除分块 O(N)\mathcal{O}(\sqrt{N}) 解决询问了。

最后附上 我的代码 以供参考。