数论基础

本文是关于在 OI 中的数论基础

作者：Shq

感谢 iShq，qwqShq，lcyz lmy 在写作过程中提供了宝贵的灵感和思想

数论函数

定义在正整数域上的函数就被成为数论函数

也就是对于数论函数 $f(n)$ 有 $n\in \mathbb{Z}^+$

积性函数

若对于数论函数 $f$ ， $\forall x,y \in \mathbb{Z}^+$ 且 $\gcd(x,y)$ 互质，有

$f ( x \times y ) = f ( x ) \times f ( y )$

就称 $f$ 为 积性函数

通过上面定义，我们可以得到

$f ( 1 ) = f ( 1 \times 1 ) = f ( 1 ) \times f ( 1 )$

可以得出对于任意的积性函数，都有 $f ( 1 ) = 1$

容易证明，对于积性函数的嵌套，逆，积，卷积得到的结果都是积性函数

卷积

我们称 $(f * g)(n)$ 是 $f,g$ 的卷积

卷积的离散定义是

$( f * g ) ( n ) = \sum _ { \tau = - \infty } ^ { \infty } f ( \tau ) g ( n - \tau )$

这里卷积的符号是 $*$ ，而不是乘的符号 $\times$ 和 $\cdot$

上面一行的 Markdown 原码:

这里卷积的符号是 $*$ ，而不是乘的符号 $\times$ 和 $\cdot$

Dirichlet 卷积

定义

我们称 $(f*g)(n)$ 是 数论函数 $f,g$ 的卷积，有

$(f * g) ( n ) = \sum _ { d | n } f ( d ) * g \left( \frac { n } { d } \right)$

性质

$\text{Dirichlet}$ 卷积的一些性质：

交换律

证明很显然...

$\begin{aligned} f * g & = \sum _ { d | n } f ( n ) g \left( \frac { n } { d } \right) \\ &= \sum _ { d | n } g ( n ) f \left( \frac { n } { d } \right)\\& = g * f \end{aligned}$

结合律

直接用交换律乱证就行了..

$\begin{aligned} ( f * g ) * h &= f * g * h \\ &= g * h * f \\&= ( g * h ) * f \\ &= f * ( g * h ) \end{aligned}$

分配律

$\begin{aligned} ( f + g ) * h & = \sum _ { d | n } [ f ( d ) + g ( d ) ] \times h \left( \frac { n } { d } \right) \\ & = \sum _ { d | n } \left[ f ( d ) \times h \left( \frac { n } { d } \right) + g ( d ) \times h \left( \frac { n } { d } \right) \right] \\ & = \sum _ { d | n } f ( d ) \times h \left( \frac { n } { d } \right) + \sum _ { d | n } g ( d ) \times h \left( \frac { n } { d } \right) \\ & = f * h + g * h \end{aligned}$

两个积性函数的卷积仍为积性函数

令两积性函数 $f,g$ 的 $\text{Dirichlet}$ 卷积为 $h$ ，那么对于任意 $x,y\in \mathbb{Z}$ 且 $\gcd(x,y)=1$ 就有

$\begin{aligned} h ( x ) \times h ( y ) & = \left( \sum _ { d _ { 1 } | x } f \left( d _ { 1 } \right) g \left( \frac { x } { d _ { 1 } } \right) \right) \left( \sum _ { d _ { 2 } | y } f \left( d _ { 2 } \right) g \left( \frac { y } { d _ { 2 } } \right) \right) \\ & = \sum _ { d _ { 1 } \left| x , d _ { 2 } \right| y } \left( f \left( d _ { 1 } \right) \times f \left( d _ { 2 } \right) \right) \times \left( g \left( \frac { x } { d _ { 1 } } \right) \times g \left( \frac { y } { d _ { 2 } } \right) \right) \\ & = \sum _ { d _ { 1 } \left| x , d _ { 2 } \right| y } f \left( d _ { 1 } d _ { 2 } \right) g \left( \frac { x y } { d _ { 1 } d _ { 2 } } \right) \\ & = \sum _ { d | x y } f ( d ) g \left( \frac { x y } { d } \right) = h ( x y ) \end{aligned}$

常用数论函数

说完了卷积和积性函数，来看看常用数论函数

常数函数

以下函数的值都是常数，用于辅助计算

元函数

$e ( n ) = [ n = 1 ]$

其中 $[\mathtt{expression}]$ 的含义是如果 $\mathtt{expression}$ 为真， $[\mathtt{expression}]$ 的值就是 $1$ ，否则为 $0$

恒等函数

$I ( n ) = 1$

单位函数

$\epsilon ( n ) = n$

数论函数

（其实上面那两个也是数论函数）

欧拉函数

欧拉函数表示在 $[1,n]$ 中与 $n$ 互质的数的个数，也就是在模 $n$ 域下的简化剩余系的大小

$\varphi ( n ) = \sum _ {i = 1} ^ {n} [\gcd(i, n) = 1]$

其中 $[\mathtt{expression}]$ 的含义是如果 $\mathtt{expression}$ 为真， $[\mathtt{expression}]$ 的值就是 $1$ ，否则为 $0$

当然，它也有更常见的形式

$\varphi ( x ) = x \prod _ { i = 1 } ^ { n } \left( 1 - \frac { 1 } { p _ { i } } \right)$

约数个数函数

$\tau ( n ) = \sum _ { k | n } 1$

约数和函数

${ \sigma ( n ) = \sum _ { k | n } k }$

除数函数

奇怪的名字（

$\sigma _ { k } ( n ) = \sum _ { d | n } d ^ { k }$

显然地，

$\sigma _ { 1 } ( n ) = \sigma ( n ) \\ \sigma _ 0 ( n ) = \tau ( n )$

至于为什么要用 $\sigma$ ，其实 $\sigma$ 是 $\Sigma$ 的小写形式，如果写过 MathJax / LaTeX就知道吧（（

莫比乌斯函数

对于 $ $n = p _ { 1 } ^ { c _ { 1 } } \times p _ { 2 } ^ { c _ { 2 } } \times \cdots \times p _ { m } ^ { c _ { m } }$ $ ，有

$\mu ( n ) = \left\{ \begin{array} { l l } { 1 } & { n = 1 } \\ { ( - 1 ) ^ { m } } & { \prod _ { i = 1 } ^ { m } c _ { i } = 1} \\ { 0 } & { \text { otherwise } \left( k _ { i } > 1 \right) } \end{array} \right.$

性质

1. 元函数与另外数论函数的卷积仍然为那个函数

$\begin{aligned} ( f * e ) ( n ) &= \sum _ { d | n } f ( d ) e \left( \frac { n } { d } \right) \\ \quad &= \sum _ { d | n } f ( d ) \left[ \frac { n } { d } = 1 \right] \\ &= \sum _ { d | n } f ( d ) [ n = d ] \\ &= f ( n ) \end{aligned}$

通过上面的东西我们就可以得出狄利克雷卷积的单位元为 $e$

2. $ $\mu * I = e$ $

$\begin{aligned} ( \mu * I ) ( n ) & = \sum _ { d | n } \mu ( d ) I ( \frac n d ) \\ & = \sum _ { d | n } \mu ( d )\end{aligned}$

首先，对于 $n=1$ 的情况显然 $( \mu * I ) ( 1 ) = 1 = e ( 1 )$

我们令 $n = p _ { 1 } ^ { c _ { 1 } } \times p _ { 2 } ^ { c _ { 2 } } \times \cdots\times p _ { m } ^ { c _ { m } }$ ，考虑它的因子 $d = p _ { 1 } ^ { x _ { 1 } } \times p _ { 2 } ^ { x _ { 2 } } \times \cdots\times p _ { m } ^ { x _ { m } }$

由于 $\mu(d)$ 中只有 $\prod _ {i=1}^m x_i=1$ 的项对它有贡献，所以我们只要统计这个的个数就好了 =w=

注意到，对于 $d$ 的唯一分解形式， $x_i$ 表示 $p_i$ 取或不取，这就变成了一个组合计数问题..

令 $r = \sum _ { i = 1 } ^ m x _ i$ ，也就是 $x_1\to x_m$ 中 $x_i$ 为 $1$ 的数量，就有

$\sum _ { d | n } \mu ( d ) = \sum _ { r = 0 } ^ { m } \left( \begin{array} { l } { m } \\ { r } \end{array} \right) ( - 1 ) ^ { r } ( n \neq 1 )$

有组合数基础的同学都知道，上式中右边就是当 $x=1,y=-1$ 时的二项式定理，即

$\begin{aligned} \sum _ { d | n } \mu ( d ) & = \sum _ { r = 0 } ^ { m } \left( \begin{array} { l } { m } \\ { r } \end{array} \right) ( - 1 ) ^ { r } \\ & = [1 + ( - 1 ) ] ^ m \\ & = 0\end{aligned}( n \neq 1 )$

莫比乌斯反演

定义及证明

对于数论函数 $f,g$ 满足

$f(n) = \sum _ {d | n} g(d)$

我们就可以通过莫比乌斯反演使用 $f$ 表示出 $g$ ，反演式子如下

$g ( n ) = \sum _ { d | n } \mu \left( \frac { n } { d } \right) f ( d ) = \sum _ { d | n } \mu ( d ) f \left( \frac { n } { d } \right)$

证明很简单......这里附上两种证明

证明 I :（通过卷积来证明）

$\begin{aligned} f ( n ) &= \sum _ { d | n } g ( d ) \\ &= \sum _ { d | n } g(d) \times I ( \frac n d )\end{aligned}$

这显然是一个卷积的形式，也就是

$\begin{aligned} f & = g * I \\ f * \mu &= g * I * \mu \\ &= g * ( I * \mu) \\ & = g * e = g \end{aligned}$

证明 II：

从右往左推，

$\begin{aligned} & \sum _ { d | n } \mu ( d ) f \left( \frac { n } { d } \right) \\ = & \sum _ { d | n } \mu ( d ) \sum _ { i | \frac { n } { d } } g ( i ) \\ = & \sum _ { i | n } g ( i ) \sum _ { k | \frac { n } { i } } \mu ( k ) \\ = & g ( n ) \end{aligned}$

故原式成立

几个常见的形式

$F ( n ) = \sum _ { n | d } f ( d ) \Rightarrow f ( n ) = \sum _ { n | d } \mu \left( \frac { d } { n } \right) F ( d )$

看到的时候有点自闭......显然直接求是不行的......

我们考虑把这个东西转化为带 $\sum \mu$ 的形式.....

令 $k = \frac d n$

$\begin{aligned} f ( n ) & = \sum _ { k = 1 } ^ { + \infty } \mu ( k ) F ( n k ) \\ & = \sum _ { k = 1 } ^ { + \infty } \mu ( k ) \sum _ { n k | t } f ( t ) \\&= \sum _ { n | t } f ( t ) \sum _ { k | \frac { t } { n } } \mu ( k ) \end{aligned}$

注意到我们这里有一个 $\sum _ { k | \frac { t } { n } } \mu ( k )$ 所以说当且仅当 $\frac t n =1$ 时，式子的值不为零，就得到了

$\sum _ { n | t } f ( t ) \sum _ { k | \frac { t } { n } } \mu ( k ) = f ( n )$

应用

1. 求

$\sum _ { i = 1 } ^ { a } \sum _ { j = 1 } ^ { b } [ g c d ( i , j ) = k ]$

我们令 $S(a,b)$ 表示上面的和式

令 $f(d)$ 表示 $\gcd(i,j)=d$ 时 $(i,j)$ 的对数， $F(d)$ 表示 $d|\gcd(i,j)$ 时 $(i,j)$ 的对数，则

$\begin{aligned} F ( d ) &= \sum _ { i = 1 } ^ { \left\lfloor \frac { n } { k } \right\rfloor } \sum _ { j = 1 } ^ { \left\lfloor \frac { m } { k } \right\rfloor } [ d | g c d ( i , j ) ] \\& = \sum _ { i = 1 } ^ { \left\lfloor \frac { n } { k } \right\rfloor } \sum _ { j = 1 } ^ { \left\lfloor \frac { m } { k } \right\rfloor } [ d | i \wedge d | j ] \\ & = \left\lfloor \frac { n } { k d } \right\rfloor \left\lfloor \frac { m } { k d } \right] \end{aligned}$

我们对上面这个式子反演一下，就有

$\begin{aligned} f ( d ) &= \sum _ { d | i } F ( i ) \mu \left( \frac { i } { d } \right) \\ & = \sum _ { d | i } \mu \left( \frac { i } { d } \right) \left\lfloor \frac { n } { k i } \right\rfloor \left\lfloor \frac { m } { k i } \right\rfloor \end{aligned}$

取 $d = 1$ ，有

$S ( n , m ) = f ( 1 ) = \sum _ { i = 1 } ^ { \min \left( \left\lfloor \frac { n } { k } | , \left\lfloor \frac { m } { k } \right\rfloor \right) \right.} \mu ( i ) \left\lfloor \frac { n } { k i } \right\rfloor \left\lfloor \frac { m } { k i } \right\rfloor$

后面的数论分块就可以做了.....

数论基础

数论基础

目录

数论函数

积性函数

卷积

Dirichlet 卷积

定义

性质

常用数论函数

常数函数

数论函数

性质

莫比乌斯反演

定义及证明

几个常见的形式

应用