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)
$$
同理可以运用线性筛计算。