线性筛

线性筛

线性筛用于在 \(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);}}}
}

\[ \]