- 线性筛
- 埃氏筛
- 对于每个数\(x\)，枚举其倍数，将\(kx\)筛去。
- 在埃氏筛过程中，每个数都会被筛掉多次，且对于每个数x，枚举其倍数的次数为\(\frac{n}{x}\)
- 故埃氏筛的时间复杂度为\(\sum_{i=1}^{n}\frac{n}{i}=n\sum_{i=1}^{n}\frac{1}{i}=n ln(n)\)
- 欧拉筛
- 在埃氏筛中，每个数会被筛掉多次，想要进一步下降复杂度，我们要求每个数只会被筛一次。
- 要想将多种筛去\(x\)的方法固定（唯一）。我们就要采用一种方法—“最小表示法”，套用在这里就是每个数被自己的最小质因子筛去。
- 首先，为了优化时间复杂度，我们不难发现，并不需要对每个\(x\)，把每个\(x\)的所有倍数都筛一遍，只需要将\(pri_kx\)，(\(pri_k \leq x\))筛去即可。
- 证明：
- 一个数\(x\)要被筛去，\(x\)必然是合数，\(x=ab\)，\((a<b<x)\) ，令\(a\)为质数，当我们用\(b\)筛时，一定能够筛去\(x=ab\)。
- 然后我们要求每个数都被自己最小质因数筛去，则当我们用\(b\)筛时，设b的最小质因子为\(pri_b\)，对于\(pri_i \leq pri_b\)，我们筛掉\(pri_i b\)就是被自己的最小值因数\(pri_i\)筛去。
- 常见积性函数
- 欧拉函数 (\(\varphi(x)\))
- \(\varphi(x)\)为积性函数
- \(\varphi(x)\)的两种计算式：
- \(\varphi(x)\) = \(\varphi(a)*\varphi(b)\) (a,b互质)
- \(\varphi(x)\) = \(x\prod_{i=1}^{k}(1-\frac{1}{p_i})\)
- 套用欧拉筛筛法，每个数都被自己最小质因子筛去，就有两种情况：
- 该数最小质因子\(pri\)的次数为\(1\)，即\(x=pri\sum_{i=2}^{k}p_i^{r_i}\)
- 直接套用积性函数的定义式\(\varphi(x)\) = \(\varphi(pri)*\varphi(\frac{x}{pri})\) (\(pri\)与\(\frac{x}{pri}\)互质)
- 该数最小质因子\(pri\)的次数\(>1\)，即x= \(pri^{r_1} * \sum_{i=2}^{k} pi^{ri}\)
- 由\(\varphi(x)\)的定义式知\(\varphi(x) = x \prod_{i=1}^{k} (1- \frac{1}{pi})\)
- \(\frac{x}{pri}\)与\(x\)没有增加额外的质因子
- 所以 \(\varphi(x) = pri * \frac{x}{pri} \prod_{i=1}^{k}(1- \frac{1}{pi})\) = \(pri *\varphi (\frac{x}{pri})\)
- 代码
- 莫比乌斯函数\(\mu(x)\)
- \(\mu(x)\)定义式: \(\mu(x)\begin{cases}1,x=1\\(-1)^k,x=\prod_{i=1}^kp_i\\0,x=\prod_{i=1}^kp_i^{r_i},\exist r_i>1\end{cases}\)
- \(\mu(x)=\mu(a)*\mu(b)\) (\(a,b\)互质)
- 套用欧拉筛筛法
- 当该数最小质因子\(pri\)，次数为\(1\)，同\(\varphi(x)\), \(\mu(x) =\mu(pri)*\mu(\frac{x}{pri})\)
- 当该数最小质因子pri，次数>1， \(\mu(x)=0\)
转载于:https://www.cnblogs.com/shjrd-dlb/p/10798239.html
