线性筛
线性筛用于在 \(O(n)\) 的时间复杂度内快速求解积性函数的前 \(n\) 项。缺点明显，空间复杂度 \(O(n)\)。
常见函数的线性筛都是基于线性筛质数，以下从筛质数开始讲解。
原理
基本线性筛
从另一个熟悉的算法出发，埃氏筛法思路简单粗暴：枚举一个数的所有倍数，并将其标记为合数。
时间复杂度同样优秀，但依然会枚举很多重复元素。
相对于埃氏筛，线性筛的特点是，它确保每个合数只被它的“最小质因数”筛掉一次。
实现方法就是字面意思，枚举当前求出的所有质数，将这些质数 \(p\) 作为倍数去乘当前数 \(i\)。
那如何保证“最小质因数”呢？从小到大枚举 \(p\) 的时候，如果 \(p|i\) 则直接停止即可。
积性函数筛
欧拉函数
这时考虑与线性筛相似的一个问题：如何通过 \(\varphi(i)\) 求出 \(\varphi(i\times p)\) （\(p\) 为小于等于 \(i\) 的质数）。
分情况讨论：
-
\(p\mid i\)：
设 \(i=p^k\times m\quad(\gcd(m,p)=1)\)：
将 \(\varphi(i)\) 展开：
\[\varphi(i)=\varphi(p^k\times m)=\varphi(p^k)\times \varphi(m)=p^{k-1}(p-1)\times\varphi(m)\tag1 \]将 \(\varphi(i\times p)\) 展开：
\[\varphi(i\times p)=\varphi(p^{k+1}\times m)=\varphi(p^{k+1})\times\varphi(m)=p^k(p-1)\times\varphi(m)=p(p^{k-1}(p-1)\times\varphi(m))\tag2 \]将 \(1\) 式中的 \(p^{k-1}(p-1)\times\varphi(m)=\varphi(i)\) 代入 \(2\) 式：
\[\varphi(i\times p)=p\times\varphi(i) \] -
\(p\nmid i\)：
根据欧拉函数的积性：
\[\varphi(i\times p)=\varphi(i)\times\varphi(p)=\varphi(i)\times(p-1) \]
莫比乌斯函数
依据莫比乌斯函数的定义：
\[\mu(n)=\begin{cases}
1\quad n=1\\
0\quad \text{存在相同质因子}\\
(-1)^k\quad (k=\text{互异质因子数量})
\end{cases}
\]
则分类讨论，对于当前枚举数 \(i\)，枚举质因子 \(p\) 有：
- 若 \(i\) 为质数，\(\mu(i)=-1\)。
- 若 \(p\mid i\) ，由于原本就含有 \(p\) 质因子，现在多乘一个，\(\mu(i\cdot p)=0\)。
- 若 \(p\nmid i\)，现在是第一个 \(p\) 质因子，所以 \(\mu(i\cdot p) = -\mu(i)\)
实现
void init() {for (int i = 1;i <= maxn;i ++) book[i] = 1;book[0] = book[1] = 0;mu[1] = phi[1] = 1ll;for (int i = 2;i <= maxn;i ++) {if (book[i] == 1) {prime[++ pcnt] = i;mu[i] = -1,phi[i] = i - 1;}for (int j = 1;j <= pcnt && i * prime[j] <= maxn;j ++) {book[i * prime[j]] = 0;if (i % prime[j] == 0) { // p 为 i的最小质因子mu[i * prime[j]] = 0;phi[i * prime[j]] = phi[i] * prime[j];break;} else {mu[i * prime[j]] = -mu[i];phi[i * prime[j]] = phi[i] * (prime[j] - 1);}}}
}
\[
\]