数论求和基础技巧

在上一节中，我们看到了莫比乌斯反演在消去 \(\gcd\)，或是 \(\epsilon\) 的限制时强大的能力。这些能力同样可以被用来处理更多的数论求和问题，但并不是所有的数论求和都有着简洁的封闭形式（事实上，通常没有），那么首先要问出的问题就是：

• 什么样的形式是我们需要的 / 是可以快速计算的？
• 为了得到这样的形式，我们需要作什么样的变换？

交换求和号

交换求和号，替换求和对象对于和式的处理有着重要的作用。

其原则为“入内求交，出外求并”。

形式化地说：

\[ \sum_{i\in A}\sum_{j\in B(i)}a_{i,j}=\sum_{j\in \cup_{i\in A}B(i)}\sum_{i\in\{i\in A\mid j\in B(i)\}}a_{i,j} \]

• 出外求并：哑指标 \(j\) 在由内层移动到外层的时候，取值范围是所有内层可取范围的并集

• 入内求交：哑指标 \(i\) 在由外层移动到内层的时候，取值范围是外层可取范围，交上所有会统计到 \(j\) 的 \(i\)。

  这一条在多元的情况下会更加显然：

  \[ \sum_{i\in A}\sum_{j\in B(i)}\sum_{k\in C(i)} \]

  那么在将 \(i\) 移动到最内层的时候，它既要能统计到 \(j\)，又要能统计到 \(k\)，是统计到 \(j\) 的 \(i\) 集合与统计到 \(k\) 的 \(i\) 集合的并集。

左边的含义是显然的，对所有数集 \(A\) 中的 \(i\)，找到依赖于 \(i\) 的约束的数集 \(B(i)\)，再枚举每个 \(j\in B(i)\) 来求和。

现在，我们要先枚举所有 \(j\)，\(j\) 的枚举范围就是所有 \(B_i\) 之并，在确定了 \(j\) 之后，找到所有 \(j\in B(i)\) 的 \(i\)，也就是它会被哪些 \(i\) 统计到。

可这个技巧有什么用？

例一

求：

\[ \sum_{i=1}^{n}\sum_{d|i}d \]

直接暴力做是 \(\mathcal O(n\sqrt n)\) 的，考虑先枚举 \(d\)，那么 \(d\) 所有的取值就是 \(1\sim n\) 之间，而每个 \(d\) 只会被其倍数枚举到：

\[ \sum_{d=1}^{n}\sum_{d|i,i\le n}d \]

后面那个求和号和 \(d\) 没关系，提出来：

\[ \sum_{d=1}^{n}d\sum_{d|i,i\le n}1 \]

显然，这是：

\[ \sum_{d=1}^{n}d\lfloor\frac{n}{d}\rfloor \]

例二

求：

\[ \sum_{i=1}^{n}\varphi(i)\left\lfloor\frac{n}{i}\right\rfloor \]

\(\left\lfloor\frac{n}{i}\right\rfloor\) 让我们联想到 \(n\) 以内 \(i\) 的倍数，那就变成倍数：

\[ \sum_{i=1}^{n}\sum_{i|j,j\le n}\varphi(i) \]

交换求和号，先枚举 \(j\)，那内层就应该是所有能枚举到 \(j\) 的哑指标 \(i\)。

\[ \sum_{j=1}^{n}\sum_{i\mid j}\varphi(i) \]

我们知道 \(\varphi*\mathbf{I}=\text{id}\)，所以原式即为：

\[ \sum_{j=1}^nj=\binom{n+1}{2} \]

顺带一提，这个式子还等于

\[ \sum_{i=1}^{n}\sum_{j=1}^{\lfloor\frac{n}{i}\rfloor}\varphi(j) \]

如果你第一步就尝试去交换求和号就会算出这个东西。

鉴于前几步中没有用到任何的 \(\varphi(n)\) 函数性质，我们有：

\[ \sum_{i=1}^{n}\sum_{j=1}^{\lfloor\frac{n}{i}\rfloor}f(i)=\sum_{i=1}^{n}\sum_{j=1}^{\lfloor\frac{n}{i}\rfloor}f(j)=\sum_{i=1}^{n}\sum_{d\mid i}f(d) \]

整除分块

我们时常能见到形如：

\[ \sum_{i=1}^{n}g(\lfloor\frac{n}{i}\rfloor) f(i) \]

的和式。假设 \(g\) 的单点值，\(f\) 的前缀和复杂度是 \(\mathcal O(1)\) 的，那么这个式子可以 \(\mathcal O(\sqrt n)\) 求出。

这是因为 \(\lfloor\frac{n}{i}\rfloor\) 至多只有 \(2\sqrt n\) 个不同的值，证明类似约数个数，分类讨论即可。当 \(i\le \sqrt n\) 时，\(\lfloor\frac{n}{i}\rfloor\) 显然只有 \(\sqrt n\) 个值，当 \(i>\sqrt n\) 时，\(\lfloor\frac{n}{i}\rfloor\le \sqrt n\)，也只有 \(\sqrt n\) 个值。

事实上，这个 \(\mathcal O(\sqrt n)\) 个数分别是 \(1,2,3,\cdots, \lfloor\sqrt n\rfloor,\left\lfloor\frac{n}{\lfloor\sqrt n\rfloor}\right\rfloor,\left\lfloor\frac{n}{\lfloor\sqrt n\rfloor-1}\right\rfloor,\cdots, \left\lfloor\frac{n}{2}\right\rfloor,n\)。

有了这个结论，怎么实现这个做法呢？有结论：

对于固定的 \(n,l\)，令 \(\lfloor\frac{n}{r}\rfloor=\lfloor\frac{n}{l}\rfloor\) 的最大的 \(r\) 的值为：

\[ \left\lfloor\frac{n}{\left\lfloor\frac{n}{l}\right\rfloor}\right\rfloor \]

记 \(\operatorname{segl}(n,d)\) 表示所有 \(1\sim n\) 的数 \(k\) 中，\(\lfloor\frac{n}{k}\rfloor=\lfloor\frac{n}{d}\rfloor\) 的最小的 \(k\)。记 \(\operatorname{segr}(n,d)\) 是最大的那个 \(k\)。

证明：

\(\lfloor\frac{n}{l}\rfloor\le \frac{n}{l}\)，从而有 \(\frac{n}{\lfloor\frac{n}{l}\rfloor}\ge \frac{n}{\frac{n}{l}}\)。

也就是

\[ \left\lfloor\frac{n}{\left\lfloor\frac{n}{l}\right\rfloor}\right\rfloor\ge \left\lfloor l \right\rfloor=l \]

也就是说，对于满足 \(\lfloor\frac{n}{l}\rfloor =k\) 的所有 \(l\)，总有 \(\lfloor\frac{n}{k}\rfloor\ge l\)。

由于这个技巧将 \(1\sim n\) 中的数 \(i\) 按 \(\lfloor\frac{n}{i}\rfloor\) 分成了若干个块（区间），所以被称为整除分块，或数论分块。

例三 / P2511 Problem B

给出 \(N,M\)，求：

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

Solution

\(\epsilon(\gcd(i,j))\) 是难求的，但 \(\displaystyle \sum_{d\mid \gcd(i,j)}\epsilon(d)\) 显然为 \(\mathbf {I}\)。将求和对象变换为 \(\mu*\mathbf{I}\)：

\[ \sum_{i=1}^{N}\sum_{j=1}^{M}\displaystyle \sum_{d\mid \gcd(i,j)}\mu(d) \]

继续作变换：

\[ \begin{aligned} &\phantom{;=}\sum_{i=1}^{N}\sum_{j=1}^{M}\displaystyle \sum_{d\mid \gcd(i,j)}\mu(d)\\ &=\sum_{i=1}^{N}\sum_{j=1}^{M}\sum_{d\mid i,d\mid j}\mu(d)\\ &=\sum_{d=1}^{\min(N,M)}\mu(d)\sum_{i=1}^{\lfloor\frac{N}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{M}{d}\rfloor}1&交换求和号\\ &=\sum_{d=1}^{\min(N,M)}\mu(d)\lfloor\frac{N}{d}\rfloor\lfloor\frac{M}{d}\rfloor \end{aligned} \]

对于 \([\gcd(i,j)=k]\) 的更为一般的情况，只要我们全部枚举的都是 \(k\) 的倍数即可。也就是，变为

\[ \sum_{i=1}^{\lfloor\frac{N}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{M}{k}\rfloor}\displaystyle [\gcd(i,j)=1] \]

二重整除分块

有时我们会遇到这种求和：

\[ \sum_{i=1}^{n}f(i)\sum_{j=1}^{\left\lfloor\frac{n}{i}\right\rfloor}g\left(\left\lfloor\frac{n}{ij}\right\rfloor\right) \]

我们知道，\(\left\lfloor\frac{n}{ij}\right\rfloor=\left\lfloor\frac{\left\lfloor\frac{n}{i}\right\rfloor}{j}\right\rfloor\)。所以这也可以写成：

\[ \sum_{i=1}^{n}f(i)\sum_{j=1}^{\left\lfloor\frac{n}{i}\right\rfloor}g\left(\left\lfloor\frac{\left\lfloor\frac{n}{i}\right\rfloor}{j}\right\rfloor\right) \]

一个直白的想法是，内层用到的值都只与 \(\lfloor\frac{n}{i}\rfloor\) 相关，那么我们对外层整除分块，对每个内层 \(\lfloor\frac{n}{i}\rfloor\) 就固定了，再施一次整除分块即可。但问题是，这种做法的复杂度是什么？

我们仍然设 \(f,g\) 的求值都是 \(\mathcal O(1)\) 的。按照 \(i\le \sqrt n\) 与 \(i> \sqrt n\) 分为两个部分：

计算：

\[ \begin{aligned} T(n)&=\sum_{i=1}^{\sqrt {n}}\mathcal O\left(\sqrt \frac{n}{i}\right)+\sum_{i=1}^{\sqrt n}\mathcal O\left(\sqrt i\right)\\ &\le \mathcal O\left(\int_1^{\sqrt n}\left(\sqrt i+\sqrt\frac{n}{i}\right)\operatorname{d}i\right)\\ &=\mathcal O(n^{\frac{3}{4}}) \end{aligned} \]

只能用来计算吗？

整除分块为我们揭示了整个序列 \(g(i)=f(\lfloor\frac{n}{i}\rfloor)\) 只有 \(\mathcal O(\sqrt n)\) 个位置的值是非平凡的，即 \(g(i)\neq g(i-1)\)。当我们在处理一长串的 \(\texttt{=}\) 号时，差分总是一个不错的选择。我们将序列差分掉，现在它只有 \(\mathcal O(\sqrt n)\) 个位置 \(\neq 0\) 了！

总结

重新清点一下，我们现在拥有的求和手段已经有：

1. 求数论函数 \(g\) 与积性函数 \(f\) 的狄利克雷卷积的前 \(n\) 项 - \(\mathcal O(n\log \log n)\)。
2. 求积性函数的前 \(n\) 项 - \(\mathcal O(n)\)。
3. 求数论函数 \(f\) 与 \(g\) 的 \(\gcd\) 卷积与 \(\operatorname{lcm}\) 卷积。
4. 整除分块 - \(\mathcal O(\sqrt n)\)。
5. 求积性函数的第 \(n\) 项前缀和 - \(\mathcal O(n)\)，但在下一节中会提到更好的做法。

有了这些工具，我们已经可以开始尝试解决很多问题。

在实践中，我们利用和式变换凑出上述的形式，同时尝试施上述方法即可。

附注：特殊函数的性质

1. \(\varphi*\mathbf{I}=\mathbf{id}\)。
2. \(d(\prod_{i=1}^{n}a_i)=\displaystyle\sum_{p_1|a_1}\displaystyle\sum_{p_2|a_2}\cdots\sum_{p_n|a_n}[\forall i,j,\gcd(p_i,p_j)=1]\)。其中 \(d(n)\) 是 \(n\) 的因数个数。

附注：反演一定更好吗？

考虑最开始的练习一，对于 \(N=M\) 的情况，可以不反演：

\[ \begin{aligned} &\phantom{;=}\sum_{i=1}^{N}\sum_{j=1}^{N}[\gcd(i,j)=1]\\ &=2\times(\sum_{i=1}^{N}\sum_{j=1}^{i}[\gcd(i,j)=1])-1\\ &=2\times(\sum_{i=1}^{N}\varphi(i))-1 \end{aligned} \]

从而预处理后可以 \(\mathcal O(1)\) 回答询问，而不用再次整除分块。经过一些讨论，这同样可以处理 \(N\ge M\) 的情况。所以一定要在充分分析性质后再考虑反演。

练习

练习 1 / P5221. Product

给你一个数 \(n\)，求：

\[ \prod_{i=1}^{n}\prod_{j=1}^{n}\frac{\operatorname{lcm}(i,j)}{\gcd(i,j)}\pmod {104857601} \]

\(1\le n\le 10^6\)，\(104857601\) 是一个质数。原本的时限为 \(200\text{ms}\)，空间限制为 \(16\text{MB}\)。

Solution

\[ \begin{aligned} \prod_{i=1}^{n}\prod_{i=1}^{n}\frac{\operatorname{lcm}(i,j)}{\gcd(i,j)} &= \prod_{i=1}^{n}\prod_{i=1}^{n}\frac{ij}{\gcd^2(i,j)}\\ &= \frac{\prod_{i=1}^{n}i^n\prod_{j=1}^{n}j}{\gcd^2(i,j)}\\ &= \frac{(n!)^{2n}}{\gcd^2(i,j)}\\ \end{aligned} \]

上面的部分是平凡的，接下来处理乘积

\[ \prod_{i=1}^{n}\prod_{j=1}^{n} \gcd(i,j) \]

经典地，枚举 \(\gcd\) 有

\[ \prod_{d=1}^{n}d^{\sum_{i=1}^{n}\sum_{j=1}^{n}[\gcd(i,j)=d]} \]

那么讨论指数就好了，我们要对 \(1\sim N\) 内的每个 \(d\) 求出

\[ \sum_{i=1}^{n}\sum_{j=1}^{n}[\gcd(i,j)=d] \]

直接套用 Problem B 的做法就可以得到一个 \(\mathcal O(n\sqrt n)\) 的做法，用 \(\sum_{i=1}^{n}2\varphi(n)-\epsilon(n)\) 来求就直接线性了，但这会被卡空间。我们快进到 Problem B 最后的式子

\[ \sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)\left\lfloor\frac{n}{k}\right\rfloor^{2} \]

我们要对每个 \(d\) 求一次，所以这是二重整除分块，这部分复杂度是 \(\mathcal O(n^{3/4})\)。非常好的一点是，\(\mu(n)\) 的前缀和非常小，可以用 int16_t 存，这样空间就够了。

回到原来的式子，现在变成了

\[ \prod_{d=1}^{n}d^{\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)\left\lfloor\frac{n}{k}\right\rfloor^{2}} \]

对于 \(\lfloor\frac{n}{d}\rfloor\) 相同的每一段，也就是指数相同的每一段，底数贡献是

\[ \frac{\operatorname{segr}(n,d)!}{(\operatorname{segl}(n,d)-1)!} \]

因为同时预处理阶乘和阶乘逆也会被卡空间，所以边整除分块，边双指针即可 \(\mathcal O(n)\) 解决这个问题。

从 \(1\) 到 \(n\) 枚举 \(d\)，整除分块的区间端点是从 \(1\) 到 \(n\) 递增的。想要线性就要预处理的是阶乘逆，阶乘边走边算。

练习 2 / P2257. YY的GCD

给你 \(n,m\)，求

\[ \sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)\in \mathbb P] \]

其中 \(\mathbb P\) 是素数集合，\(T\) 组测试数据。

\(T\le 10^4\)，\(1\le n,m\le 10^7\)

Solution

\[ \begin{aligned} \sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)\in\mathbb P] &= \sum_{i=1}^{n}\sum_{j=1}[\gcd(i,j)\in\mathbb P]\\ &= \end{aligned} \]