想不到花了两个小时的时间看 (min\_25) 筛就看懂了 实际去追了一下魔禁3
我们先举个例子。如求
其中 (f(i)) 是积性函数，而且要满足 (iin prime) 时 (f(i)) 是一个简单多项式，(f(i^k)) 可以快速计算出来。
怎么用呢
我们先丢开前缀和，计算
那么现在我们要用到埃氏筛的思想。每次我们要减去新筛去的 (f(i))，然后减完了以后就是答案
(g(n,j)) 表示在前 (j) 个质数用埃氏筛筛完后的答案。
举个例子，(g(10,2)=f(2)+f(3)+f(5)+f(7)+f(9))。令 (P_j) 为质数集合中第 (j) 小的质数，那么
现在，我们可以用 (g(n,j-1)) 来推出 (g(n,j))
若 (P_j^2>n)，那么 (P_j) 便对答案没有贡献了，(g(n,j)=g(n,j-1))
若 (P_j^2leq n)，那么我们在 (g(n,j-1)) 的基础上要减掉一些东西。
那减掉什么呢？
首先，能被 (P_j) 筛掉的数一定被 (P_j) 整除，并且在除以 (P_j) 之后，最小质因子 (geq P_j)
那么我们联想到了 (g(frac{n}{P_j},j-1))。但是发现 (P_j imes P_1,P_j imes P_2,...,P_j imes P_{j-1}) 已经被筛过了，所以要减去的应该是 (f(P_j) imes (g(frac{n}{P_j},j-1)-sum_{i=1}^{j-1}f(P_i)))
所以可以得到下面的式子：
(g(n,j)= egin{cases} g(n,j-1)&P_j^2>n\ g(n,j-1)-f(P_j) imes [g(frac{n}{P_j},j-1)-sum_{i=1}^{j-1}f(P_i)]&P_j^2leq n end{cases})
这就是 (min\_25) 筛的精髓。其实本质上 (min\_25) 是个容斥算法。
值得一提的是，它的时间复杂度为 (O(frac{n^{frac 34}}{log n}))，可以当做 (O(n^{frac 23}))，在 (nleq 10^{11}) 的数据下大概要花 (500ms) 左右。