版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
title: "笔记 - 整除分块, Dirichlet卷积, Dirichlet前缀和, 积性函数, Möbius反演, 杜教筛" categories:
整除分块, Dirichlet 卷积, Dirichlet 前缀和, 积性函数, Möbius 反演, 杜教筛
<!-- more -->在讲之前, 我们先看两个定理
$$ \forall a,b,c\in\mathbb{Z},\left\lfloor\frac{a}{bc}\right\rfloor=\left\lfloor{\left\lfloor\frac{a}{b}\right\rfloor\over c}\right\rfloor $$
注意到
$$ \frac{a}{b}=\left\lfloor\frac{a}{b}\right\rfloor+\left{ \frac{a}{b}\right} $$
其中 ${ \frac{a}{b}}$ 是 $a\over b$ 的小数部分
故
$$ \begin{aligned} \left\lfloor\frac{a}{bc}\right\rfloor&=\left\lfloor\frac{a}{b}\cdot\frac{1}{c}\right\rfloor\ &=\left\lfloor\left(\left\lfloor\frac{a}{b}\right\rfloor+\left{ \frac{a}{b}\right}\right)\frac{1}{c}\right\rfloor\ &=\left\lfloor{\left\lfloor\frac{a}{b}\right\rfloor\over c}+\left{ \frac{a}{b}\right}\frac{1}{c}\right\rfloor\ &=\left\lfloor{\left\lfloor\frac{a}{b}\right\rfloor\over c}\right\rfloor \end{aligned} $$
<a href="#p-t-1.1" id="end-t-1.1">$\Box$</a>
对任意正整数 $n$, $\lfloor\frac{n}{i}\rfloor,~i=1,2,...,n$ 的取值不超过 $\lfloor2\sqrt{n}\rfloor$ 种
即
$$ \forall n\in\mathbb{N}^*,\left|\left{\left\lfloor\frac{n}{i}\right\rfloor\big|~i=1,2,...,n\right}\right|\leqslant\lfloor2\sqrt{n}\rfloor $$
当 $i\leqslant\sqrt{n}$ 时, $\lfloor\frac{n}{i}\rfloor$ 至多有 $\sqrt{n}$ 种取值
当 $i>\sqrt{n}$ 时, 有 $\lfloor\frac{n}{i}\rfloor\leqslant\sqrt{n}$, 此时 $\lfloor\frac{n}{i}\rfloor$ 也至多有 $\sqrt{n}$ 种取值
所以 $\lfloor\frac{n}{i}\rfloor,~i=1,2,...,n$ 至多有 $\lfloor2\sqrt{n}\rfloor$ 种取值
<a href="#p-t-1.2" id="end-t-1.2">$\Box$</a>
整除分块主要是用于快速求 $\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor$ 的算法
朴素求法的时间复杂度自然是 $O(n)$
为了方便叙述, 我们举个例子:
令 $n=15$, $f(i)=\lfloor\frac{n}{i}\rfloor$ 我们可列出下表
| $f(i)$ | $i$ 的范围 |
|---|---|
| 15 | $[1,1]$ |
| 7 | $[2,2]$ |
| 5 | $[3,3]$ |
| 3 | $[4,5]$ |
| 2 | $[6,7]$ |
| 1 | $[8,15]$ |
我们可以发现, $f$ 任一像对应的原象是一段区间, 所以我们可以考虑直接求出对应区间长度, 从而就能快速求值
该算法的流程如下:
关键就在于如何求 $r$
令 $\lfloor\frac{n}{l}\rfloor=k_l$, 不难发现
$$ r=\max_{ik_l\leqslant n}{i} $$
显然
$$ r=\left\lfloor\frac{n}{k_l}\right\rfloor=\left\lfloor{n\over{\lfloor\frac{n}{l}\rfloor} }\right\rfloor $$
<details open> <summary><font color='orange'>Show code</font></summary> {% icodeweb blog lang:cpp nt-2/get_sum.cpp %} </details>由 <a href="#t-1.2">定理 - 1.2</a> 可知是 $O(\sqrt{n})$
如何求 $\sum_{i=1}^{\min{m,n}}\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{j}\rfloor$
只需令
$$ r=\min\left{\left\lfloor{n\over{\lfloor\frac{n}{l}\rfloor} }\right\rfloor,\left\lfloor{m\over{\lfloor\frac{m}{l}\rfloor} }\right\rfloor\right} $$
如何求 $\sum_{i=1}^n\lfloor\frac{n}{ai+b}\rfloor$
令 $\lfloor\frac{n}{al+b}\rfloor=k_l$, 不难发现
$$ r=\max_{aik_l\leqslant n-bk_l}{i} $$
显然
$$ r=\left\lfloor\frac{n-bk_l}{ak_l}\right\rfloor $$
定义 $A$ 为对其上元素定义了加法, 减法和乘法的非空集(或 $A$ 是交换环), 则称函数 $f:\mathbb{N}\to A$ 为数论函数
通俗来说就是满足如下要求的函数:
在后面的积性函数一章中也会提到许多例子
如果某个数论函数具有简单的表达式 $f(n)$, 在不引起歧义的情况下我们也可以将其简写为 ${f(n)}$, 如 ${1}$, ${n}$
对数论函数 $f,g$, 定义其 Dirichlet 卷积为 $f*g$, 满足:
$$ (f*g)(n):=\displaystyle\sum_{d\mid n}f(d)g(\frac{n}{d}) $$
如
$$ (f*g)(10)=f(1)g(10)+f(2)g(5)+f(5)g(2)+f(10)g(1) $$
令 $f,g,h$ 是数论函数
下面对结合律进行证明
{% post_link draft-001 另一篇证明 %}
令 $f,g,h$ 是数论函数, 则
$$ f(gh)=(fg)h $$
$$ \begin{aligned} (f(gh))(n)&=\sum{a\mid n}f(a)\sum{b\mid\frac{n}{a}}g(b)h(\frac{n}{ab})\ &=\sum{abc=n}f(a)g(b)h(c)\ &=\sum{a\mid n}\left(\sum_{b\mid a}f(b)g(\frac{a}{b})\right)h(\frac{n}{a})\ &=((fg)h)(n) \end{aligned} $$
<a href="#p-t-3.1" id="end-t-3.1">$\Box$</a>
证明略
用于解决如下问题: 给出 $a_1,a_2,\dots,a_n$, 求 $b_1,b_2,\dots,b_n$, 其中
$$ bi=\sum{j\mid i}a_j $$
设 $x,y$ 的分解分别为 $x=\prod_ip_i^{\alpha_i}, y=\prod_ip_i^{\beta_i}$
则 $a_x$ 对 $b_y$ 有贡献当且仅当 $\forall i,\alpha_i\leqslant\beta_i$
预先筛出 $[1,n]$ 中的素数即可更快地处理
<details open> <summary><font color='orange'>Show code</font></summary> {% icodeweb blog lang:cpp nt-2/Dirichlet_sum.cpp %} </details>分析方法和 Eratosthenes 筛法一致, 为 $O(n\log\log n)$
满足 $\forall m, n\in\Bbb{N}^+,(m,n)=1\implies f(mn)=f(m)f(n)$ 的 $f(n)$
$f,g$ 为积性函数 $\implies\ fg,\displaystyle\frac{f}{g},f*g$ 为积性函数
即积性函数关于乘法, 除法, 卷积封闭
下面给出性质 1 的证明
$f,g$ 为积性函数 $\implies\ fg,\displaystyle\frac{f}{g},f*g$ 为积性函数
此处只给出 $f*g$ 是积性函数的证明
令 $h=f*g$, $(m,n)=1$, 则
$$ \begin{aligned} h(mn)&=\sum{d\mid mn}f(d)g(\frac{mn}{d})\ &=\sum{d1\mid m}\sum{d_2\mid n}f(d_1d_2)g(\frac{m}{d_1}\frac{n}{d2})\ &=\sum{d1\mid m}\sum{d_2\mid n}f(d_1)f(d_2)g(\frac{m}{d_1})g(\frac{n}{d2})\ &=\left(\sum{d_1\mid m}f(d_1)g(\frac{m}{d1})\right)\left(\sum{d_2\mid n}f(d_2)g(\frac{n}{d_2})\right)\ &=h(m)h(n) \end{aligned} $$
<a href="#p-t-4.1" id="end-t-4.1">$\Box$</a>
Euler 函数和 Möbius 函数积性的证明在后面给出, 下面给出 $\tau$ 和 $\sigma$ 积性的证明
$\tau(n)$ 和 $\sigma(n)$ 是积性函数
令 $m,n$ 为两互素正整数, 则
$$ \tau(mn)=\sum_{d1\mid m}\sum{d2\mid n}1=\left(\sum{d1\mid m}1\right)\left(\sum{d_2\mid n}1\right)=\tau(m)\tau(n) $$
$$ \sigma(mn)=\sum_{d1\mid m}\sum{d_2\mid n}d_1d2=\left(\sum{d_1\mid m}d1\right)\left(\sum{d_2\mid n}d_2\right)=\sigma(m)\sigma(n) $$
<a href="#p-t-4.2" id="end-t-4.2">$\Box$</a>
设 $n$ 的标准分解式为 $n=\prod_{i=1}^rp_i^{\alpha_i}$, 则
$$ \tau(n)=\prod_{i=1}^r(\alpha_i+1) $$
$$ \sigma(n)=\prod_{i=1}^r{p_i^{\alpha_i+1}-1\over p_i-1} $$
<a href="#ifr-4.3" id="end-ifr-4.3">$\Box$</a>
满足 $\forall m, n\in\Bbb{N}^+,f(mn)=f(m)f(n)$ 的 $f(n)$
记作 $\varphi(n)$, 指的是 $[1,n]$ 中所有与 $n$ 互素的数
若 $p$ 为素数, $a$ 为自然数, 则 $\varphi(p^a)=p^a-p^{a-1}$
特别地, $\varphi(p)=p-1$
(1,3 的推论) 设 $n=\prod_{i=1}^{\omega(n)}p_i^{\alpha_i}$, 则
$$ \varphi(n)=\prod_{i=1}^{\omega(n)}p_i^{\alpha_i}\left(1-\frac{1}{pi}\right)=n\prod{i=1}^{\omega(n)}\frac{p_i-1}{p_i} $$
当 $n>2$ 时, $\varphi(n)$ 为偶数
下面给出性质 1 的证明
$\varphi(n)$ 是积性函数
设 $n,m$ 是互素的正整数, 我们将 ${0,1,...,mn-1}$ 如下列出
$$ \begin{matrix} 0&1&...&m-1\ m&m+1&...&2m-1\ \vdots&\vdots&\ddots&\vdots\ (n-1)m&(n-1)m+1&...&mn-1 \end{matrix} $$
考察第 $j$ 列的数 $im+j,~i=0,1,...,n-1$, 其均属于模 $m$ 的同余类 $\overline{j},~j=0,1,...,m-1$, 故共有 $\varphi(m)$ 列中的数与 $m$ 互素
考察第 $j$ 行的数 $in+j,~i=0,1,...,m-1$, 其均属于模 $n$ 的同余类 $\overline{j},~j=0,1,...,n-1$, 故共有 $\varphi(n)$ 行中的数与 $m$ 互素
不难发现, 只有同时在这 $\varphi(m)$ 列和 $\varphi(n)$ 行中的数才和 $mn$ 互素
故 $\varphi(mn)=\varphi(m)\varphi(n)$
<a href="#p-t-5.1" id="end-t-5.1">$\Box$</a>
单个数
按 $\varphi(n)=n\prod_{i=1}^{\omega(n)}\frac{p_i-1}{p_i}$ 计算即可
<details open> <summary><font color='orange'>Show code</font></summary> {% icodeweb blog lang:cpp nt-2/euler_phi_single.cpp %} </details>筛法 (以 Euler 筛为例)
依据积性和 $\varphi(p^a)=p^a-p^{a-1}$ 计算
<details open> <summary><font color='orange'>Show code</font></summary> {% icodeweb blog lang:cpp nt-2/euler_phi_seive.cpp %} </details>记作 $\mu(n)$, 设 $n=\prod_{i=1}^{\omega(n)}p_i^{\alpha_i}$, 则
$$ \mu(n)=\begin{cases} 0,&\exists i\in[1,\omega(n)],~s.t.~\alpha_i>1\ (-1)^{\omega(n)},&otherwise \end{cases} $$
或者说, $\mu(n)$ 满足如下条件:
若 $n$ 中有平方因子, 则 $\mu(n)=0$
平方因子即满足 $\exists a\in\mathbb{Z}^*, a^2\mid n$ 的因子
显然, $n$ 中有平方因子等价于 $n$ 中有平方素因子
若 $n$ 中无平方因子, 则 $\mu(n)=(-1)^{\omega(n)}$, $\omega(n)$ 即为 $n$ 的本质不同素因子个数
$$ \sum_{d\mid n}\mu(d)=\epsilon(n) $$
即
$$ \mu*{1}=\epsilon $$
(2 的推论) $\displaystyle[(x,y)=1]=\sum_{d\mid (x,y)}\mu(d)$
下面给出性质 1 和性质 2 的证明
$\forall m,n\in\mathbb{N}^*,~(m,n)=1\implies\mu(mn)=\mu(m)\mu(n)$
设 $n,m$ 是互素的正整数, 若 $m$ 或 $n$ 有平方因子, 则 $\mu(mn)=0=\mu(m)\mu(n)$
否则, 设
$$ m=\prod_{i=1}^rpi,n=\prod{i=1}^sq_i $$
其中 $p_1,p_2,\dots,p_r,q_1,q_2,\dots,q_s$ 是两两不同的素数
从而 $mn=(\prod_{i=1}^rpi)(\prod{i=1}^sq_i)$ 是 $r+s$ 个不同素数的乘积, 有
$$ \mu(mn)=(-1)^{r+s}=(-1)^r(-1)^s=\mu(m)\mu(n) $$
<a href="#p-t-6.1" id="end-t-6.1">$\Box$</a>
$$ \mu*{1}=\epsilon $$
令
$$ f(n)=(\mu*{1})(n)=\sum_{d\mid n}\mu(d) $$
易得 $f(1)=\mu(1)=1$
接下来不妨令 $n$ 为大于 $1$ 的整数, 下面给出两种证法
对于大于 $1$ 的整数 $n$ 做标准分解 $n=\prod_{i=1}^rp_i^{\alpha_i}$, 则 $f(n)$ 是 $\mu(d)$ 的和, 其中 $d$ 是 $p_1,p_2,\dots,p_r$ 中一部分素数的乘积
令 $D_{i}$ 表示 $p_1,p_2,\dots,p_r$ 中某 $i$ 个数的乘积构成的集合, 则 $\forall d\in D_i,~\mu(d)=(-1)^i$
而
$$ |D_i|=\binom{r}{i}=\frac{r!}{i!(r-i)!} $$
因此
$$ f(n)=\sum_{i=1}^r\binom{r}{i}(-1)^i=(1-1)^r=0 $$
<a href="#p-t-6.2-1" id="end-t-6.2-1">$\Box$</a>
由 $f=\mu*{1}$ 可知, $f$ 必为积性函数
另一方面, $\epsilon$ 也为积性函数
因此, 我们只需证
$$ \forall p\in\text{Prime}^+,\forall\alpha\in\mathbb{N}^*,~f(p^{\alpha})=\epsilon(p^{\alpha}) $$
对上述的 $p$ 和 $\alpha$, 一方面, $\epsilon(p^{\alpha})=0$
另一方面,
$$ \begin{aligned} f(p^{\alpha})&=\sum_{i=0}^{\alpha}\mu(p^i)\ &=\mu(1)+\mu(p)\ &=0 \end{aligned} $$
因此命题得证
<a href="#p-t-6.2-2" id="end-t-6.2-2">$\Box$</a>
单个数
很少出现, 直接按定义即可
筛法 (以 Euler 筛为例)
基于积性和定义
<details open> <summary><font color='orange'>Show code</font></summary> {% icodeweb blog lang:cpp nt-2/mobius_seive.cpp %} </details>对于数论函数 $f,g$, 有
$$ f=g{1}\iff g=f\mu $$
或者写成
$$ \forall n\in\mathbb{N}^*,~f(n)=\sum{d\mid n}g(d)\iff g(n)=\sum{d\mid n}f(d)\mu\left(\frac{n}{d}\right) $$
如果用卷积证明的话十分简洁
$$ f=g{1}\iff f\mu=g{1}\mu=g*\epsilon=g $$
但这里我们给出不使用卷积运算法则的证明方法, 因为这是交换求和次序的绝佳练习, 交换求和次序也是应用 Möbius 反演解题的重要操作
在这里复述一遍命题
$$ \forall n\in\mathbb{N}^*,~f(n)=\sum_{d\mid n}g(d)\tag{1} $$
$$ \forall n\in\mathbb{N}^*,~g(n)=\sum_{d\mid n}f(d)\mu\left(\frac{n}{d}\right)\tag{2} $$
我们要证的即为 $(1)\iff(2)$
先证 $(1)\implies(2)$
若 $(1)$ 成立, 则有
$$ \sum{d\mid n}f(d)\mu\left(\frac{n}{d}\right)=\sum{d\mid n}\sum_{e\mid d}g(e)\mu\left(\frac{n}{d}\right)\tag{3} $$
之后我们交换求和号, 即改变元素的枚举顺序
当前 $(3)$ 式是先枚举 $n$ 的因子 $d$, 再枚举 $d$ 的因子 $e$
我们要改写成先枚举 $n$ 的因子 $e$, 再枚举 $d$, 此时的 $d$ 是 $n$ 的因子, 同时也是 $e$ 的倍数
从而在交换求和号之后变为
$$ \sum{e\mid n}\sum{e\mid d\mid n}g(e)\mu\left(\frac{n}{d}\right)=\sum{e\mid n}g(e)\sum{e\mid d\mid n}\mu\left(\frac{n}{d}\right)\tag{4} $$
为什么要这么做呢?
这样做是因为 $\displaystyle\sum_{e\mid d\mid n}\mu\left(\frac{n}{d}\right)$ 是可以很容易求出来的, 具体操作如下:
令 $d'=\frac{d}{e}$, 则条件 $e\mid d\mid n$ 等价于 $d'\mid\frac{n}{e}$
而
$$ \frac{n}{d}=\frac{n}{e}\cdot\frac{e}{d}={ \frac{n}{e}\over d'} $$
因此固定 $e$, 则有
$$ \begin{aligned} \sum{e\mid d\mid n}\mu\left(\frac{n}{d}\right)&=\sum{d'\mid\frac{n}{e}}\mu\left({ \frac{n}{e}\over d'}\right)\ &=\sum_{d'\mid\frac{n}{e}}\mu\left(d'\right)\ &=\epsilon(d') \end{aligned} $$
此式表明 $\displaystyle\sum_{e\mid d\mid n}\mu\left(\frac{n}{d}\right)$ 只有在 $e$ 取 $n$ 时才为 $1$, 其余时为 $0$
所以 $(4)$ 式的最终结果即为 $g(n)$, 此时命题 $(2)$ 成立
我们把步骤合并起来
若 $(1)$ 成立, 则有
$$ \begin{aligned} \sum{d\mid n}f(d)\mu\left(\frac{n}{d}\right)&=\sum{d\mid n}\sum{e\mid d}g(e)\mu\left(\frac{n}{d}\right)\ &=\sum{e\mid n}\sum{e\mid d\mid n}g(e)\mu\left(\frac{n}{d}\right)\ &=\sum{e\mid n}g(e)\sum{e\mid d\mid n}\mu\left(\frac{n}{d}\right)\ &\xlongequal{d'=d/e}\sum{e\mid n}g(e)\sum{d'\mid\frac{n}{e}}\mu\left({ \frac{n}{e}\over d'}\right)\ &=\sum{e\mid n}g(e)\sum{d'\mid\frac{n}{e}}\mu(d')\ &=\sum{e\mid n}g(e)\epsilon(d')\ &=\sum_{e\mid n}g(e)\epsilon\left(\frac{d}{e}\right)\ &=g(n) \end{aligned} $$
类似可证 $(1)\impliedby(2)$, 简要列出步骤
$$ \begin{aligned} \sum{d\mid n}g(d)&=\sum{d\mid n}\sum{e\mid d}\mu\left(\frac{d}{e}\right)f(e)\ &=\sum{e\mid n}f(e)\sum{e\mid d\mid n}\mu\left(\frac{d}{e}\right)\ &\xlongequal{d'=d/e}\sum{e\mid n}f(e)\sum_{d'\mid\frac{n}{e}}\mu(d')\ &=f(n) \end{aligned} $$
<a href="#p-t-7.1" id="end-t-7.1">$\Box$</a>
提示: $d(ij)=\sum{x\mid i}\sum{y\mid j}[(x,y)=1]$
杜教筛是一种在亚线性时间复杂度的求数论函数前缀和的算法
首先我们有如下定理
设 $f,g$ 是数论函数, $S(n):=\sum_{i=1}^nf(i)$, 则
$$ g(1)S(n)=\sum{i=1}^n(f*g)(i)-\sum{i=2}^ng(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right) $$
$$ \begin{aligned} \sum{i=1}^n(f*g)(i)&=\sum{i=1}^n\sum{d\mid i}f(d)g\left(\frac{i}{d}\right)\ &=\sum{d=1}^ng(d)\sum{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i)\ &=\sum{d=1}^ng(d)S\left(\left\lfloor\frac{n}{d}\right\rfloor\right)\ &=g(1)S(n)+\sum_{i=2}^ng(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right) \end{aligned} $$
<a href="#p-t-8.1" id="end-t-8.1">$\Box$</a>
如果我们选取的 $g$, 使 $\sum_{i=1}^n(f*g)(i)$ 和 $g$ 的前缀和都能方便地算出来, 那么我们就可以方便地算出 $S(n)$
$ \begin{array}{l|l} 1 & \textbf{function} ~ \texttt{sum_of_f}(n)\ 2 & \qquad a \gets \texttt{sum_of_f*g}(n) \ 3 & \qquad l \gets 2\ 4 & \qquad \textbf{while} ~ l \leqslant n \ 5 & \qquad \qquad r \gets \left\lfloor {n \over \left\lfloor \frac{n }{l} \right\rfloor} \right\rfloor\ 6 & \qquad \qquad a \gets a-(\texttt{sum_of_g}(r)-\texttt{sum_of_g}(l-1))\cdot\texttt{sum_of_f}(\left\lfloor \frac{n }{l} \right\rfloor)\ 7 & \qquad \qquad l \gets r+1\ 8 & \qquad \textbf{end} ~ \textbf{while} \ 9 & \textbf{return} ~ a \ \end{array} $
设求出 $S(n)$ 的时间函数为 $T(n)$, 则
$$ \begin{aligned} O(T(n))&=O\left(\sum_{i=1}^{\sqrt n}\left(O(\sqrt{i})+O\left(\sqrt\frac{n}{i}\right)\right)\right)\ &=O\left(\int_1^{\sqrt{n}}\left(\sqrt{x}+\sqrt\frac{n}{x}\right)\mathrm{d}x\right)\ &=O(n^\frac{3}{4}) \end{aligned} $$
如果我们能够预处理出 $S(i),~i=1,2,...,m$, 设预处理的时间复杂度为 $O(W(m))$, 则时间复杂度可变为
$$ \begin{aligned} O(T(n))&=O\left(\sum_{i=1}^{\lfloor\frac{n}{m}\rfloor}O\left(\sqrt\frac{n}{i}\right)+W(m)\right)\ &=O\left(\int_1^{\lfloor\frac{n}{m}\rfloor}\sqrt\frac{n}{x}\mathrm{d}x+W(m)\right)\ &=O\left(\frac{n}{\sqrt m}+W(m)\right) \end{aligned} $$
以线性筛作为预处理方式为例, 此时 $O(W(m))=O(m)$
由平均值不等式可知, 当 $m=(\frac{n}{2})^\frac{2}{3}$ 时, 其时间复杂度最小, 为 $O(n^\frac{2}{3})$
$$ \frac{n}{\sqrt m}+m=\frac{n}{2\sqrt m}+\frac{n}{2\sqrt m}+m\geqslant\sqrt[3]{\frac{n}{2\sqrt m}\cdot\frac{n}{2\sqrt m}\cdot m}=\sqrt[3]{\frac{n^2}{4}} $$
当 $\frac{n}{2\sqrt m}=m$, 即 $m=(\frac{n}{2})^\frac{2}{3}$ 时取得最小值