数论函数 学习笔记

数论函数&&莫比乌斯反演&&杜教筛

1.各种积性函数

单位函数：

\epsilon(n)=[n=1]=\begin{equation} \left\{ \begin{array}{**lr**} 1,\quad n=1 \\ 0,\quad n\neq0 \end{array} \right. \end{equation}

Id函数

$id_k(n)=n^k$

其中记$Id(x)=id_1(x)=x$

除数函数：

$\sigma_k(n)=\sum_{d|n}d^k$

其中$\sigma_0(n)$常记为$d(n)$，约数和$\sigma_1(n)$常记为$\sigma(n)$。

欧拉函数：

$\phi(n)=n\cdot\prod^s_{i=1}\big(1-\frac{1}{p_i} \big)$

其中$n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_s^{\alpha_s}$

欧拉函数有如下性质

$n=\sum_{d|n}\phi(d)$

或：$Id=\phi*1$

证明：把1到n的整数按与n的最大公约数分类

若$gcd(n,i)=d$，那么$gcd(\frac n d,\frac i d)=1$。

又$\frac n d\geqslant\frac i d$ ，这样的$\frac i d$有$\phi(\frac n d)$ 个

所以i有$\phi(\frac n d)$个。

因此

$n=\sum_{d|n}\phi(\frac n d)=\sum_{d|n}\phi(d)$

因为$\frac n d$和d遍历的n的约数。

莫比乌斯函数：

\mu(n)=\begin{equation} \left\{ \begin{array}{**lr**} 1,\quad n=1 \\ (-1)^s, n=p_1p_2\cdots p_s\\ 0,\quad otherwise \end{array} \right. \end{equation}

其中otherwise表示n有平方因子。

性质：

$\sum_{d|n}\mu(d)=\epsilon(n)$

即

$\mu*1=\varepsilon$

证明：

$n=1$时显然成立

$n>1$ ,设$\pi(n)=s$，当$\mu(d)\neq0$时，d的每个素因子质数为0或1

可以从中选出k个指数为1，选法共有$\binom s k$种。

所以,根据二项式定理,有（请走这边)

$\sum_{d|n}\mu(d)=\sum^s_{k=0}(-1)^k\binom s k =(1-1)^s=0$

得证

2.狄利克雷卷积

$h(n)=\sum_{d|n}f(d)g(\frac n d)$

记作$h=f*g$

性质：

单位函数$\varepsilon$是狄利克雷卷积的单位元，即$f*\varepsilon=f$

狄利克雷卷积满足交换律和结合律

如果$f,g$都是积性函数，那么$f*g$也是积性函数

证明：

设$n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_s^{\alpha_s}$，那么有

$f(n)=\alpha _1f(p_1)\alpha _2f(p_2)\cdots \alpha _sf(p_s)\\ g(n)=\alpha _1g(p_1)\alpha _2g(p_2)\cdots \alpha _sg(p_s)\\ h(n)=f*g=\alpha_1(f(1)+g(n))+\alpha_2(f(p_1)+g(\frac n {p_1}))+\cdots\\=\alpha_1 h(p_1))\alpha _2h(p_2)\cdots \alpha _sh(p_s)$

常用卷积：$\mu*1=\epsilon,Id=\phi*1$

3.莫比乌斯反演

莫比乌斯变换

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

称g是f的莫比乌斯变换，f是g的莫比乌斯逆变换。

也记作$g=f*1$。

莫比乌斯反演定理

$g(n)=\sum_{d|n}f(d)\Leftrightarrow f(n)=\sum_{d|n}g(d)\mu(\frac n d)$

证明：

$g=f*1\Leftrightarrow f=f*\varepsilon=f*1*\mu=g*\mu$

经典问题

跟定x,y,使x，y互质的数对数有多少

$\sum^n_{x=1}\sum^m_{y=1}[gcd(x,y)=1]\\= \sum^n_{x=1}\sum^m_{y=1}\sum_{d|gcd(x,y)}\mu(d)\\ =\sum^n_{x=1}\sum^m_{y=1}\sum_{d|x,d|y}\mu(d) \\ =\sum_{d|x,d|y}\sum^n_{x=1}\sum^m_{y=1}\mu(d)\\ =\sum^{min(n,m)}_{d=1}\mu(d)\left\lfloor\frac n d\right\rfloor\left\lfloor\frac m d\right\rfloor$

$\sum^n_{x=1}\sum^m_{y=1}[gcd(x,y)=1]=\sum^n_{x=1}\sum^m_{y=1}\sum_{d|gcd(x,y)}\mu(d)\\=\sum^n_{x=1}\sum^m_{y=1}\sum_{d|x,d|y}\mu(d)\\=\sum_{d|x,d|y}\sum^n_{x=1}\sum^m_{y=1}\mu(d)\\=\sum^{min(n,m)}_{d=1}\mu(d)\left\lfloor\frac n d\right\rfloor\left\lfloor\frac m d\right\rfloor$

4.杜教筛（SUM）

杜教筛是对数论函数求和的一种方式。

欧拉函数前缀和：

$\varphi(n)=\sum^n_{i=1}\phi(i)$

考虑到$Id=\phi*1$,有

$\frac 1 2n(n+1)=\sum^n_{k=1}k=\sum^n_{k=1}\sum_{d|k}\phi(d)\\ =\sum^n_{k=1}\sum_{d|k}\phi(\frac k d)\\ =\sum^n_{d=1}\sum^{\lfloor\frac n d\rfloor}_{k=1}\phi(k)=\sum^n_{d=1}\varphi(\left\lfloor\frac n d\right\rfloor)$

莫比乌斯函数前缀和：

考虑到$1=\mu*\epsilon$,有

$1=\sum^n_{k=1}\epsilon(k)=\sum^n_{k=1}\sum_{d|k}\mu(\frac k d)\\ =\sum^n_{d=1}\sum_{d|k\\k\in[1,n]}\mu(\frac k d)=\sum^n_{d=1}\sum^{\lfloor\frac nd\rfloor}_{k=1}\mu(k)=\sum^n_{d=1}M(\left\lfloor\frac n d\right\rfloor)$

一般积性函数的前缀和：

$ff$