数论学习笔记

Warning：请不要使用此博客作为学习用途，这个博客是写出来我自己看的，所以很有可能前言不搭后语。

备忘录

一些记号

$\text{I}(x)=1$

$\text{id}(x)=x$

$\text{e}(x)=[x=1]$

$\text{d}(x)=\sum\limits_{d|x}1$

$\sigma(x)=\sum\limits_{d|x}d$

$\varphi(x)$ 欧拉函数

$\mu(x)$ 莫比乌斯函数

一些数论定理

$e*F=F$，$F$ 为任何数论函数。

$e=\mu * 1$，$[n=1]=\sum\limits_{d|n}\mu(d)$

$id=\varphi*1$，$n=\sum\limits_{d|n}\phi(d)$

$\mu*id=\varphi$

$\mu*d=1$

$id=\varphi *1$

莫比乌斯反演

$\text{g}(n)=\sum\limits_{d|n}{\text{f}(n)}$，则 $\text{f}(n)=\sum\limits_{d|n}\mu({\frac{n}{d}})\text{g}(d)$

狄利克雷卷积

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

Euler 函数的前缀和

令 $\phi(n)=\sum\limits_{i=1}^n\varphi(i)$，求 $\phi(n)$。

$$\begin{aligned}{} &\quad \frac{1}{2}n(n+1)\\ &=\sum\limits_{i=1}^{n}i=\sum\limits_{i=1}^n\sum\limits_{d|i}\varphi(\frac{i}{d})\\ &=\sum\limits_{d=1}^n\sum\limits_{1\leq i \leq n, d|k}\varphi(\frac{i}{d})\\ &=\sum\limits_{d=1}^{n}\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\varphi(i)\\ &=\sum\limits_{d=1}^n\phi(\lfloor \frac{n}{d}\rfloor)\\ \end{aligned}\\ \therefore \phi(n)=\frac{1}{2}n(n+1)-\sum\limits_{d=2}^{n}\phi(\lfloor\frac{n}{d}\rfloor)\\$$

当知道了 $\phi(\lfloor\frac{n}{d}\rfloor)$ 运用整除分块即可在 $\mathcal O(\sqrt n)$ 内算出 $\phi(n)$。

利用记忆化搜索，可以防止一个值被计算多次。

总时间复杂度 $\mathcal O(n^\frac{3}{4})$。

因此可以使用欧拉筛筛出前 $n^\frac{2}{3}$ 的值，然后运用杜教筛，那么总时间复杂度为 $\mathcal O(n^\frac{2}{3})$。显然非常玄学，我也不知道怎么计算出来的qwq

Möbius 函数的前缀和

令 $\text{M}(n)=\sum\limits_{i=1}^n\mu(i)$。计算 $\text{M}(n)$。

$$\begin{aligned} 1 &=\sum\limits_{i=1}^n\text{e}(i)=\sum\limits_{i=1}^n\sum\limits_{d|i}\mu(d)\\ &=\sum\limits_{d=1}^n\sum\limits_{1\leq i\leq n,d|i}\mu(\frac{i}{d})\\ &=\sum\limits_{d=1}^n\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\mu(i)\\ &=\sum\limits_{d=1}^n\text{M}(\lfloor\frac{n}{d}\rfloor) \end{aligned}\\ \therefore \text{M}(n)=1-\sum\limits_{d=2}^n\text{M}(\lfloor\frac{n}{d}\rfloor)$$

同理可以运用线性筛计算。

推广到一般情况

令 $\text{F}(n)=\sum\limits_{i=1}^n\text{f}(i)$。计算 $\text{F}(n)$。

$$\begin{aligned} &\sum\limits_{i=1}^n(f*g)(i)\\ =&\sum\limits_{i=1}^n\sum\limits_{d|i}f(\frac{i}{d})g(d)\\ =&\sum\limits_{d=1}^n\sum\limits_{1\leq i \leq n,d|i}f(\frac{i}{d})g(d)\\ =&\sum\limits_{d=1}^n g(d)\sum\limits_{k=1}^{\lfloor\frac{n}{d}\rfloor}f(k)\\ =&\sum\limits_{d=1}^ng(d)F(\lfloor\frac{n}{d}\rfloor) \end{aligned}\\ \therefore F(n)=\sum\limits_{i=1}^n(f*g)(i)-\sum\limits_{d=2}^ng(d)F(\lfloor\frac{n}{d}\rfloor)$$