简单数论函数和应用

参考资料

• OI-WIKI 莫比乌斯反演
• OI-WIKI 迪利克雷卷积
• 从莫比乌斯到欧拉
• 莫比乌斯反演-从基础开始

部分定义和约定

符号

• $\operatorname{id}$ ：$\operatorname{id}$ 数论函数，$\operatorname{id}(x)=x$
• $\epsilon$ : 单位函数 $\epsilon(x)=[x=1]$
• $[]$ ：中扩号表达式，中扩号内条件成立则为 $1$，否则为 $0$
• $\boldsymbol{1}$：$\boldsymbol{1}$ 函数，若 $f(n)=\boldsymbol{1}$，则 $\forall x \in N^+,f(x)=1$

数论函数

• 一个数论函数定义域为正整数，值域为复数。

• 一个数论函数为积性函数，当且仅当 $\forall (a,b),\gcd(a,b)=1\rightarrow f(a\times b)=f(a)\times f(b)$

• 一个数论函数为完全积性函数，当且仅当 $\forall a,b,f(a\times b)=f(a)\times f(b)$

迪利克雷卷积

迪利克雷卷积为数论函数的乘法操作，定义两个数论函数的迪利克雷卷积定义为

$$g=f*h,g(n)=\sum\limits_{d|n} f(d)\times h(\frac{n}{d})$$

迪利克雷卷积的除法操作就是逆操作，一般只能构造得到。

迪利克雷卷积的性质（证明见下一部分）：

• 两个积性函数的迪利克雷卷积仍是积性函数。
• 两个积性函数的迪利克雷卷积除法结果仍是积性函数。

为了方便，以下所有数论函数的乘法未经说明均为迪利克雷卷积。

常见积性函数

• 欧拉函数 $\phi(n)$
• 莫比乌斯函数 $\mu(n)$
• 约数个数函数 $d(n)$

一些结论的简单证明

迪利克雷卷积的性质

简单性质

• 积性函数 $f$，满足 $f(1)=1$

逆元存在且唯一

所有数论函数存在逆元，即对于所有 $f$，存在 $g$ 使得 $f*g=\epsilon$，直接构造对应的 $g(n)$ 即可。

$$g(n)=-\dfrac{\sum\limits_{d|n,d\neq n}{f(d)\times g(\frac{n}{d})}}{f(1)}\\ g(1)=\frac{1}{f(1)}$$

因此数论函数的逆元存在且唯一。

交换律

$f g=g f$，显然成立

结合律

$f g h=f (g h)$，成立，但不显然。

令 $f g h=f_1,f (g h)=f_2,f g=a,g h=h * g=b$

$$f_1(n)=\sum\limits_{d_1|n} a(d_1)\times h(\frac{n}{d_1})=\sum\limits_{d_1|n}\sum\limits_{d_2|d_1} f(d_2)\times g(\frac{d_1}{d_2})\times h(\frac{n}{d_1})$$ $$f_2(n)=\sum\limits_{d_1|n} b(d_1)\times f(\frac{n}{d_1})=\sum\limits_{d_1|n}\sum\limits_{d_2|d_1} h(d_2)\times g(\frac{d_1}{d_2})\times f(\frac{n}{d_1})$$

对于任意一组满足 $d_1|n,d_2|d_1$ 的 $d_1,d_2$，构造 $d_2’=\frac{n}{d_1},d_1’=\frac{n}{d_2}$ ，容易发现这样的构造是一一对应的，满足 $f(d_2)\times g(\frac{d_1}{d_2})\times (\frac{n}{d_1})=f(\frac{n}{d_1’}) \times g(\frac{d_1’}{d_2’}) \times h(d_2’))$ 。

因此对于上式中的每一项，下式都有一项与之一一对应，因此上下式相等。

分配律

$f(g+h)=fg+f*h$

显然成立。

两个积性函数的迪利克雷卷积为积性函数

$f,h$ 为积性函数，则 $f*g=h$，$h$ 为积性函数。

$\forall a,b \ , \gcd(a,b)=1\ ,h(a\times b)=h(a)\times h(b)$，满足

$$\begin{align} h(a\times b)=&\sum\limits_{d_1|a}\sum\limits_{d_2|b}f(d_1\times \frac{b}{d_2})\times g(\frac{a}{d_1}\times d_2)\\ =&\sum\limits_{d_1|a}\sum\limits_{d_2|b}f(d_1)\times f(\frac{b}{d_2})\times g(\frac{a}{d_1})\times g( d_2)\\ =&\sum\limits_{d_1|a} f(d_1)\times g(\frac{a}{d_1})\sum\limits_{d_2|b} f(\frac{b}{d_2})\times g(d_2)\\ =&h(a)\times h(b) \end{align}$$

两个积性函数的迪利克雷卷积除法为积性函数

证明 $f,h$ 为积性函数，且 $h*g=f$，则 $g$ 为积性函数。

令 $h’h=\epsilon$，则 $g=fh’$

即证明积性函数的逆元也为积性函数。

证明

使用了数学归纳法。

完全积性函数相关

若 $w$ 是完全积性函数，则

$$(g\cdot w) * (f \cdot w) = (g * f)\cdot w$$

常见的积性函数关系

• $\mu* \boldsymbol{1}=\epsilon$
• $\phi* \boldsymbol{1}=\operatorname{id}$
• $\mu * \operatorname{id} = \phi$

莫比乌斯反演

莫比乌斯反演的常见做法是用其它易于交换求和符号的项替换掉不容易求和的相关项。

不容易交换求和的项一般有 $d,\gcd$ 等。

数论分块

莫比乌斯反演或者其它数数题中常用的优化方式。

核心原理是对于 $[1,n]$ 中所有数 $i$，$\frac{n}{i}$ 的结果只有 $\sqrt{n}$ 个。

证明是容易的，对于 $[1,\sqrt{n}]$，一共有 $\sqrt{n}$ 个值，对于 $[\sqrt{n},n]$，一共也只有 $\sqrt{n}$ 个值。

枚举的方式是先枚举一个 $l$，然后计算出一个最大的 $r$，满足 $\frac{n}{r}=\frac{n}{l}$，容易证明 $r=\big\lfloor\dfrac{n}{\lfloor\frac{n}{l}\rfloor}\big\rfloor$。

for(int l=1,r=1;l<=n;l=r+1,r=n/(n/l)){
	do_something();
}

莫比乌斯函数

定义

$$\mu(n)= \begin{cases} 1&n=1\\ 0&n\text{ 含有平方因子}\\ (-1)^k&k\text{ 为 }n\text{ 的本质不同质因子个数}\\ \end{cases}$$

$\mu*\boldsymbol{1}=\epsilon$

这是核心结论了。

考虑证明 $\forall n>1,\mu(n)=0$。

考虑每个约数的贡献，显然每个质因子只需要考虑一次，如果质因子出现多次，那么根据定义贡献为 $0$。

设有 $k$ 个质因子，那么选出奇数个和选出偶数个的方案显然是相等的，所以和为 $0$。

莫比乌斯反演

一般形式

$$\begin{align} f*\bold{1}=g\iff& g*\mu=f \\ g(n)=\sum\limits_{d|n}f(d)\iff& f(n)=\sum\limits_{d|n}\mu(d)\times g(\frac{n}{d}) \end{align}$$

证明是显然的，因为 $\boldsymbol{1}*\mu=\epsilon$

常用

$[\gcd(i,j)=1]=\sum\limits_{d|\gcd(i,j)}\mu(d)$

枚举 $d$，即可快速计算。

欧拉反演

名字是杰哥取的。

常用形式

$\gcd(i,j)=\sum\limits_{d|\gcd(i,j)}\phi(d)$

证明

即证明 $\phi*\boldsymbol{1}=\operatorname{id}$ 。

也可以得到 $\operatorname{id} * \mu = \phi$。

我们只需要证明 $\phi*\boldsymbol{1}$ 在 $p^c$ 处取值为 $\operatorname{id}(p^c)$，由于 $\phi,\boldsymbol{1},\operatorname{id}$ 均为积性函数，自然在所有位置成立。

$$\begin{align} (\phi*\boldsymbol{1})(p^c)=&1+\sum _{i=1}^{c} (p-1)\times p^{i-1}\\ =& 1+\frac{p^c-1}{p-1}\times(p-1)\\ =&p^c\\ =&\operatorname{id}(p^c) \end{align}$$

筛法

介绍四大筛法。

四大筛法通常用于求一些积性函数的前缀和。

假设要求 $f$ 的前缀和。

记 $F(n) = \sum\limits_{i=1}^n f(i),H(n)=\sum\limits_{i=1}^n h(i),G(n)=\sum\limits_{i=1}^n g(i)$。

杜教筛

杜教筛的核心是构造两个容易求前缀和的函数 $g,h$，满足 $h = f * g$。

有

$$\begin{align} H(n)&=\sum\limits_{i=1}^n h(i)\\ &=\sum_{i=1}^n\sum_{d|i}g(d)f(\frac{i}{d})\\ &=\sum_{d=1}^ng(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor} f(i) \end{align}$$

将右边 $d\ge 2$ 的项移到左边

$$H(n)-\sum\limits_{d=2}^ng(d)F(\lfloor\frac{n}{d}\rfloor)=F(n)g(1)$$

$H(n)$ 是好求的，然后 $g(1)=1$，后面的项对 $n$ 数论分块。

然后有一个结论 $\big\lfloor\dfrac{\lfloor\frac{n}{a}\rfloor}{b}\big\rfloor=\lfloor\dfrac{n}{ab}\rfloor$。因此要求的项只有 $\sqrt n$ 项。

线性筛前 $n^\frac{2}{3}$ 项的前缀和，可以取到最优复杂度 $n^\frac{2}{3}$。复杂度证明见 OI-WIKI，证明。

PN(Powerful Number) 筛

定义 Powerful Number 是每个质因数质数不小于 $2$ 的数。

如果能构造一个容易求前缀和的积性函数 $g(x)$，满足 $g(p)=f(p)$，那么我们就可以在 $O(\sqrt n)$ 的时间复杂度内计算 $F(n)$。

具体的，考虑构造 $h = f / g$，所以 $f(p) = h(1)g(p) + h(p)g(1)$，由于 $g(p) =f (p)$，所以有 $h(p)$ 处取值为 $0$，由于 $g,f,h$ 都是积性函数，所以 $h$ 仅在 Powerful Number 处有取值，其余处取值为 $0$。

考虑

$$\begin{align} F(n)&=\sum_{i=1}^nf(i)\\ &=\sum_{i=1}^n\sum_{d|i}h(d)g(\frac{i}{d})\\ &=\sum_{d=1}^nh(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}g(i) \end{align}$$

枚举所有 Powerful Number，计算 $h(d)G(\lfloor\frac{n}{d}\rfloor)$ 即可，Powerful Number 的个数是 $O(\sqrt n)$ 的。

构造 $h$ 的话，可以直接用 $g * h = f$，并使用卷积的定义构造，当然，$f(p^c)$ 必须要容易求。

州阁筛