线性筛法与积性函数

学习积性函数后再观线性筛法。

[2019年5月28日] 这篇文章写完了,今后可能还会有一些零碎的修改,想到什么回来补充。

[2019年5月31日] 对一般线性函数的筛法补充了一种套路。

[2019年6月2日] 补充了约数和函数的线性筛法。

素数判定问题

一个经典问题:求区间$[1, n]$中的所有质数。

我们可以使用埃氏筛,时间复杂度$O(n \log \log n)$。

如果需要记录素数$p_i$的话,需要新开一个数组,第一层循环 i * i < maxn 也需要改为 i < maxn,这样才能遍历到所有要保存的点。

$O(n \log \log n)$是很好的。但是还有一种复杂度更优的线性算法:欧拉线性筛。

欧拉线性筛的思想是通过已经筛出的素数的倍数筛去合数,并且保证每个数被它的最小素数因子筛去。假设$p \times i$是被筛去的合数,$p$是一个素数,那么如何满足$p$是$p \times i$的最小质因子呢?那我们必须保证$p$是$i$的最小质因子,于是就有了线性筛中非常关键的一个语句 if (i % p[j] == 0) break;

积性函数

积性函数定义:对于数论函数$f(x)$,若对于$(x, y)=1$的$x$和$y$,满足$f(xy) = f(x)f(y)$,那么$f$为积性函数。如果对于任意的$x$和$y$,都能满足$f(xy) = f(x)f(y)$,则$f$为完全积性函数。

积性函数的性质:

  • 所有的积性函数都可以使用线性筛法在线性复杂度内求出。
  • 若$f$和$g$都是积性函数,那么他们的Direclet卷积$(f*g)(n) = \sum_{d|n}f(d)g(\frac{n}{d})$也是积性函数。

下面给出一些常见的积性函数线性筛法。

莫比乌斯函数

定义:

$$ \mu(n) = \left \{ \begin{aligned} & 1, &n = 1 \\ & (-1)^k , & n = p_1 p_2 p_3 \cdots p_k \\ & 0, & {\rm otherwise} \end{aligned} \right . $$

筛法考虑定义,分类讨论$\mu (i \times p_j)$:当$p_j \nmid i$的时候,$(i, p_j) = 1$,筛的时候$i \geq 2$,根据定义如果$i$可以分解成多个不同素数的乘积,$i\times p_j$相当于多加了一个素数,$(-1)^k$变成了$(-1)^{k+1}$,$\mu(i \times p_j) = \mu(i) \times (-1)$;如果$i$是上面otherwise的情况,$i \times p_j$必然是otherwise,$\mu(i \times p_j) = 0$。统一起来,可以写成$\mu (i \times p_j) = 0 – \mu(i)$。当$p_j | i$的时候,$i \times p_j$有平方因子,故$\mu(i \times p_j) = 0$。

 

欧拉函数

欧拉函数$\varphi(n)$表示不超过$n$且与$n$互质的正整数个数,根据$n$的标准分解并结合容斥原理,

$$\varphi(n) = n \prod_{i = 1}^{s} \left( 1 – \frac{1}{p_i} \right)$$

其中$n =\prod_{i = 1}^{s} p_i^{a_i}$。求和的过程就是对$\varphi (i \times p_j)$进行讨论,当$p_j \nmid i$时,$(i, p_j) = 1$,根据积性函数性质$\varphi (i \times p_j) = \varphi(i) \times \varphi(p_j)$,这一点十分显然。当$p_j | i$时,$\varphi (i \times p_j) = \varphi(i) \times p_j$,可以通过欧拉函数的定义来证明,根据定义:

$$\varphi(i \times p_j) = i \times p_j \prod_{k = 1}^{s_1} \left( 1 – \frac{1}{p_k} \right)$$

$$\varphi(i) = i \prod_{k = 1}^{s_2} \left( 1 – \frac{1}{p_k} \right) $$

而由于$p_j$是$i$的质因子,所以$\prod_{k = 1}^{s_1} \left( 1 – \frac{1}{p_k} \right) =\prod_{k = 1}^{s_2} \left( 1 – \frac{1}{p_k} \right) $,所以$\varphi (i \times p_j) = \varphi(i) \times p_j$。

 

 

约数个数和

约数个数和函数是除数函数$\sigma_{k} (n) = \sum_{ d | n } d^k$ 在 $k = 0$时的特殊情况,记$d(n) =\sigma_{0} (n) $,表示$n$的约数个数,为积性函数。

考虑如何线性筛。根据质数唯一分解定理对于任意一个整数$x$,有

$$x = \prod_{i = 1}^{n} p_i^{a_i}$$

根据乘法计数原理,$x$的因子的个数为$\prod_{i = 1}^{n} (a_i + 1)$,因为每个$p_i$取$t_i$个,$t_i \in [0, a_i]$,共$a_i + 1$个。我们可以用一个数组$A_i$维护$i$的最小质因子的指数$a_1$,在线性筛筛素数时,当$ i \bmod p_j = 0$,这种情况下,$i$必然包含了一个$p_j$,并且$p_j$是$i$的最小质因子,那么$i \times p_j$比$i$多一个最小质因子,$t_1$的取值范围从$[0,a_1]$变成了$[0, a_1+ 1]$,所以$d_{i \times p_j} = d_i \times \frac{A_i + 2}{A_i + 1}$。

约数和

约数和函数是除数函数$k = 1$的情况:

$$ \sigma(n) = \sigma_{1} (n) = \sum_{d|n} d $$

与约数个数和类似,考虑维护标准分解中的最小项$p_{1}^{a_1}$,参考这篇文章 ICPC 2019 南昌全国邀请赛(网络赛)G题 中$\varphi * \mu$的筛法,当${\rm low(i) = i}$的时候考虑$f(p^{k+1}) = f(p^k) + p^{k + 1}$,然后按照这篇文章的套路线性筛即可。

 

三个常用关系

记$I(n) = 1$,$\epsilon(n) = [n=1]$,${{\rm Id}_k(n) = n^k}$,${\rm Id}(n) ={\rm Id}_1(n) = n$。那么:

$$ \left\{ \begin{aligned} & \mu * I = \epsilon \\ & \varphi * I = {\rm Id} \\ & \mu * {\rm Id} = \varphi \end{aligned} \right .$$

其中第一条我在博客中给出过证明:Mobius函数性质证明。第二条和第三条是莫比乌斯反演定理作用下的一对关系。

一般的积性函数的线性筛法

对于简单的积性函数,可以使用这样的套路:

  • 根据积性函数的定义$f(1)=1$
  • 考虑自变量为素数的情况,也就是$f(p)$
  • 考虑筛$i \times p_j$
    • $p_j \nmid i$时,${\rm gcd}(i, p_j) = 0$,根据积性函数的定义$f(i \times p_j) = f(i) \times f(p_j)$
    • $p_j | i$ 时,考虑$p_j$对$f(i \times p_j)$的贡献,考虑从$f(i)$转移到$f(i \times p_j)$

这里给出一道例题:2018 ICPC 南京赛区网络赛J,可以参考题解中的第二中做法。

对于复杂一些的积性函数,我们可以使用这样的套路:

维护一个函数${\rm low}(n) = p_{1} ^ {a_1}$,为$n$的标准分解的第一项,在上述$i \times p_j$情况中,如果${\rm low}(i) = i$,说明$i$是质数幂,可以从$f(p^{k – 1})$转移到$f(p^k)$,否则$\frac{i}{{\rm low}(i)}$和$p_j \times {\rm low}(i)$互质,可以通过积性函数性质求,模板如下:

这个套路可以参考我的这篇题解:ICPC 2019 南昌全国邀请赛(网络赛)G题

参考文献

1
说点什么

avatar
50
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
0 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
trackback

[…] 线性筛法与积性函数 […]