这篇文章是贾志鹏的论文，学习了以后感觉收获还是比较大吧，为了方便以后复习，记录一下。
1、Eratosthenes筛法筛素数，即大白书上的代码。
2、Euler筛法，时间复杂度O(n)。如果只是筛素数，一般两者差别不大，但这个线性复杂度的方法却是很多积性函数转化为线性复杂度所要用到的必要工具。
3、对于积性函数，如果n = ∏ (pi^ki)，那么f(n) = ∏ ( f(pi^ki) )，如果f(n)是完全积性函数，则f(n) = ∏ (f(pi) ^ ki)。
4、欧拉函数和莫比乌斯函数均为积性函数。欧拉函数，phi(p^k) = p^k � p^(k-1) = (p-1) * p^(k-1)。
5、sum_d (phi(d)) = n，对所有d|n。
6、1…n中所有和n互质的数之和为n * phi(n) / 2。
7、phi(n) = sum_d (mobius(d) * n / d)，对所有d|n。
8、sum_i (mobius(i)) = (n == 1)，对所有i|n。
9、线性筛法对欧拉函数打表。
10、线性筛法对莫比乌斯函数打表。
11、线性筛法求逆元，求f(n)在mod p的意义下的乘法逆元，若p = n*t + k，则f(n) = n * (t^2) * f(k)^2 (mod p)。
12、用O(n^0.5＋m^0.5)的复杂度，求sum (gcd (a, b))和sum (lcm(a, b))，对所有的1 <= a <= n，1 <= b <= m。
Read full article from 《线性筛法与积性函数》学习小结 | PlumRain
No comments:
Post a Comment