[学习笔记] 线性筛 积性函数
Keaven
·
·
个人记录
线性筛
每个合数被它的最小质因子 P 筛恰好一次，或者说 x 只被 \frac{x}{P(x)} 筛去，所以 O(n)。
积性函数
定义
$$
\begin{cases}
f(1)=1\\
f(xy)=f(x)f(y)\ ,\gcd(x,y)=1
\end{cases}
$$
## 基本工具
$P(x)$ 表示 $x$ 的最小质因子。
$\alpha(x)$ 表示 $x$ 的唯一分解中 $P(x)$ 的次幂。
$P\alpha(x)$ 表示 $P(x)^{\alpha(x)}$。
则有 $f(x)=f(P\alpha(x))f(\frac{x}{P\alpha(x)})$。
$P(x)$ 可以在线性筛过程中直接求。
$$
\alpha(x)=
\begin{cases}
\alpha(\frac{x}{P(x)})+1\\
1&,P(x)\not =P(\frac{x}{P(x)})
\end{cases}
$$
$$
P\alpha(x)=
\begin{cases}
P\alpha(\frac{x}{P(x)})\times P(x)\\
P(x) &,P(x)\not =P(\frac{x}{P(x)})
\end{cases}
$$
## 常见积性函数
（以下 $f(1)=1$ 不再强调）
### 欧拉函数 $\varphi(x)
$$
\varphi(x)=
\begin{cases}
\varphi(\frac{x}{P(x)})\times P(x)\\
\varphi(\frac{x}{P(x)})\times (P(x)-1)
&,P(x)\not =P(\frac{x}{P(x)})
\end{cases}
$$
或
$$
\varphi(x)=\varphi(\frac{x}{P\alpha(x)})
\times P\alpha(x)
\times \frac{(P(x)-1)}{P(x)}
$$
### 莫比乌斯函数 $\mu(x)
正整数 n=\prod_{i=1}^k p_i^{a_i}，那么 \mu(n)=\begin{cases}(-1)^k\\0&,\max a>1\end{cases}
\mu (x) =
\begin{cases}
-[\alpha(x)=1]&,x=P\alpha(x)\\
\mu(P\alpha(x))\mu(\frac{x}{P\alpha(x)})
\end{cases}
约数个数函数 d(x)
$$
d(x)=d(\frac{x}{P\alpha(x)})\times(\alpha(x)+1)
$$
### 幂函数 $\mathrm{id}_ k(x)
\mathrm{id}_ k(n)=n^k
\mathrm{id}_ k(x)=
\begin{cases}
\mathrm{id}_ k(\frac{x}{P(x)})\times P(x)\\
x^k &,x=P(x)
\end{cases}
复杂度 O(\frac{n}{\ln n}\times \log k)=O(n)。
约数的幂和 \sigma_k(x)
\sigma_k(n)=\sum_{i|n}{i^k}
\sigma_k(x)=\sigma_k(\frac{x}{P\alpha(x)})\times
\frac{P(x)^{k(\alpha(x)+1)}-1}{P(x)^k-1}
对 P(x) 的每种值预处理 P(x)^k，复杂度 O(\frac{n}{\ln n}\times \log k)=O(n)。
与给定数的最大公约数 \gcd(x,k)
\gcd(x,k)=
\begin{cases}
gcd(\frac{x}{P(x)},k)\times P(x)
&,P(x)\mid \frac{k}{gcd(\frac{x}{P(x)},k)}
\\
gcd(\frac{x}{P(x)},k)
\end{cases}