AC. 梦想

frank_c1

数论相关线性筛

发布于2016年03月09日 | 暂无评论 | 720阅读 | 数论

数论问题中,有许多函数需要我们进行线性预处理。利用欧拉筛法这个强大的算法,我们可以解决某些函数的线性筛。一般情况下,在数论题目中,如果我们要对一个函数线性筛,首先需要证明这个函数是积性函数。

积性函数是什么呢?在数论中,对于某函数f(x),若对任意两个互质的正整数a,b,有f(ab) = f(a)f(b),则称这个函数是积性函数;特别地,若对于任意两个正整数a,b,有f(ab) = f(a)f(b),则称这个函数是完全积性函数。完全积性函数一定是积性函数。

先来一些完全积性函数:特殊的常函数f(n)=1,单位函数f(n) = n;幂函数f(n) = n ^ k。再来一些常用的积性函数:莫比乌斯函数\mu(n),欧拉函数\phi(n),最大公约数(a固定)\gcd(a,n),约数个数d(n),约数和s(n),约数的k次幂之和s_k(n)

如何判定一个函数是否是积性函数呢?有几种方法简单的方法:

1.如果h(n) = f(n)g(n),且f(n)g(n)均为积性函数,则h(n)为积性函数。

2.如果f(n)是积性函数,则\sum_{d|n} {f(n)}是积性函数。

3.如果f(n)g(n)均为积性函数,则f(n)g(n)的狄利克雷卷积是积性函数。

证明了函数是积性后,就需要运用欧拉筛法来求解。我们需要在适当的时机求出每个变量的函数值。分析欧拉筛法,为什么它是线性的?因为它保证每个合数仅被筛去一次,且是被它最小的质因数筛去的。这是一个很重要的性质。先来看一段运用欧拉筛法线性筛的模板:

大致来说,质数的情况比较好处理,因为这是边界情况,一般我们能够O(1)求得函数在质数情况下的函数值;在满足积性时(即ipr[j]互质)也好处理,根据定义直接将函数值相乘即可;麻烦在于不满足积性时(两数不互质),此时需要具体情况具体分析,可以手推找规律,也可以通过观察解析式找出关键点。

我们来分析几个常用积性函数的线性筛过程:

莫比乌斯函数

根据莫比乌斯函数定义,n=质数时,\mu(n) = -1;不满足积性时,有\mu(n)=0

欧拉函数

根据欧拉函数定义,n=质数时,有n-1个正整数与它互质。不满足积性时,需要用到一个结论:若整数an互质,那么a+nn仍然互质;若整数an不互质,那么a+nn仍然不互质;故此时i \times pr[j]的欧拉函数值为phi[i] \times pr[j]

约数个数

这个函数在不满足积性情况时比较难处理,我们考虑到求约数的公式d(n) = \prod_{i=1}^{k} {p_i ^ {a_i}},可以维护一个辅助函数MinPower(n),为n的最小质因子的次数。则在n=质数时,d(n) = 2,MinPower(n) = 1;在不满足积性时,d(i \times pr[j]) = d(i) \frac{MinPower(i)+2} {MinPower(i)+1},注意MinPower(n)的处理也要同步进行。

约数和

约数和与上面的约数个数比较相似,但是更麻烦一些,也需要维护一个辅助函数。MinProd(n)表示n只含有n最小质因子的最大约数。则n=质数时,s(n) = n + 1,MinProd(n) = n。在不满足积性时,如果i=MinProd(i),那么显然只会增加一个约数i \times pr[j],直接累加即可;如果i \neq MinProd(i),我们将ipr[j]这两个不满足积性的整数变成满足积性的,即s(i \times pr[j]) = s(\frac{i} {MinProd(i)}) s(pr[j] MinProd(i))。还是一样,MinProd(n)的处理一定要同步进行。

最后来小结一下:

1.线性筛一定要先证明函数是积性的,否则要考虑拆分函数。

2.线性筛的过程中要考虑三个部分:质数,满足积性,不满足积性。

3.不满足积性的部分不好处理;我们可以考虑挖掘函数本身的性质或增加辅助函数来寻求突破口。