「数论」数论基础笔记

数论基础

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

数论函数

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

也就是对于数论函数 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 原码:

1
这里卷积的符号是 $*$ ,而不是乘的符号 $\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

  1. \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 )

应用

\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

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

坚持原创技术分享,您的支持将鼓励我继续创作!