2020-01-02 20:16 已编辑四川大学 C++

关注

min_25筛

$min-25$

用于求 $\sum ^ n _ {i = 1} f(i)$ ，复杂度“据说”是 $O(n^{3/4}/logn)$ ，会比杜教筛略快

$f$ 需满足 $f$ 是积性函数，且 $f(p^k)$ 是关于 $p$ 的低次多项式（如果次数过高，需要用拉格朗日插值求系数） $min-25$ 中定义了两个函数： $g, S$

$g$ 是质数位上的前缀和， $S$ 就是答案。

$g$

$g_k(n, j) = \sum \limits _{i = 2} ^ n i ^ k [i \in P \ or \ minp(i)> p_j]$

$g_k(n, 0) = \sum \limits _{i = 2} ^ n i ^ k$

$g_k(n, j) = \begin{cases} g_k(n, j - 1) - p_j^k (g_k(\lfloor \frac n {p_j} \rfloor, j - 1)\ -\ \sum \limits ^{j - 1} _ {x = 1} p_x^k) \ & \ p_j^2 \leq n \\ g_k(n, j - 1) \ &\ p_j^2 > n\\ \end{cases}$

$g(n) = \sum a_kg_k(n, cur)$

$S$

$S(n, j) = \sum \limits _{x = 2} ^ n f(x) [minp[x] \ge p_j]$

$S(n, j) - S(n, j + 1) = \sum \limits _{x = 2} ^n f(x) [p_j \le minp(x) < p_{j + 1}]$

$= \sum \limits _{x = 2} ^n f(x) [minp(x) == p_j]$

$= \sum \limits _{e = 1} ^{p_j^e \leq n} f(p_j^e) \sum \limits _{x = 2, p_j^e | x} ^n f(\frac x {p_j^e}) [minp(\frac x {p_j^e}) \ge p_{j + 1} \ or\ \frac x {p_j^e} == 1]$

$= \sum \limits _{e = 1} ^{p_j^e \leq n} f(p_j^e) (1+\sum \limits _{x = 2} ^{\lfloor \frac n {p_j^e} \rfloor} f(x) [minp(x) \ge p_{j + 1}])$

$= \sum \limits _{e = 1} ^{p_j^e \leq n} f(p_j^e) (1+ S(\lfloor \frac n {p_j^e} \rfloor, j + 1))$

$= f(p_j) (1+ S(\lfloor \frac n {p_j} \rfloor, j + 1)) + \sum \limits _{e = 2} ^{p_j^e \leq n} f(p_j^e) (1+ S(\lfloor \frac n {p_j^e} \rfloor, j + 1))$

$= f(p_j) + f(p_j)S(\lfloor \frac n {p_j} \rfloor, j + 1)) + \sum \limits _{e = 2} ^{p_j^e \leq n} f(p_j^e) (1+ S(\lfloor \frac n {p_j^e} \rfloor, j + 1))$

$= f(p_j) + \sum \limits _{e = 1} ^{p_j^e \leq n} f(p_j^e) S(\lfloor \frac n {p_j^e} \rfloor, j + 1) + \sum \limits _{e = 2} ^{p_j^e \leq n} f(p_j^e)$

$= f(p_j) + \sum \limits _{e = 1} ^{p_j^e \leq n} f(p_j^e) S(\lfloor \frac n {p_j^e} \rfloor, j + 1) + \sum \limits _{e = 1} ^{p_j^{e + 1} \leq n} f(p_j^{e + 1})$

又当 $\lfloor \frac n {p_j^e} \rfloor \ge p_{j + 1} > p_j$ 即 $p_j^{e + 1} < n$ 时 $S(\lfloor \frac n {p_j^e} \rfloor, j + 1)$ 才不为 $0$ , 故

$= f(p_j) + \sum \limits _{e = 1} ^{p_j^{e + 1} < n} f(p_j^e) S(\lfloor \frac n {p_j^e} \rfloor, j + 1) + \sum \limits _{e = 1} ^{p_j^{e + 1} \leq n} f(p_j^{e + 1})$

$= f(p_j) + \sum \limits _{e = 1} ^{p_j^{e + 1} \leq n} (f(p_j^e) S(\lfloor \frac n {p_j^e} \rfloor, j + 1) + f(p_j^{e + 1}))$ ，因为 $S(p_j,j +1) = 0$

当 $p_j > n$ 时 $S(n,j) = 0$ ，将上式求和，得：

$S(n, j) = \sum \limits _{k \ge j} ^ {p_k \le n} (f(p_k) + \sum \limits _{e = 1} ^{p_k^{e + 1} \leq n} (f(p_k^e) S(\lfloor \frac n {p_k^e} \rfloor, k + 1) + f(p_k^{e + 1})))$

$= g(n) - g(p_{j - 1}) + \sum \limits _{k \ge j} ^ {p_k \le n}\sum \limits _{e = 1} ^{p_k^{e + 1} \leq n} (f(p_k^e) S(\lfloor \frac n {p_k^e} \rfloor, k + 1) + f(p_k^{e + 1}))$

$= g(n) - g(p_{j - 1}) + \sum \limits _{k \ge j} ^ {p_k^2 \le n}\sum \limits _{e = 1} ^{p_k^{e + 1} \leq n} (f(p_k^e) S(\lfloor \frac n {p_k^e} \rfloor, k + 1) + f(p_k^{e + 1}))$

$min-24$

将 $min-25$ 的过程改为递推，可以求出所有给 $S(n / d)$

$S'$

$S'(n, j) = \sum \limits _{x = 2} ^ n f(x) [x \in P \ or \ minp[x] \ge p_j]$

$if\ p_j ^2 > n, S'(n, j) - S'(n, j + 1) = 0.$

$else$

$S'(n, j) - S'(n, j + 1) = \sum \limits _{x = 2} ^n f(x) [p_j \le minp(x) < p_{j + 1} \ and \ x \ is \ not \ a \ \ prime]$

$= \sum \limits _{x = 2} ^n f(x) [minp(x) == p_j \ and \ x \ is \ not \ a \ \ prime]$

$= \sum \limits _ {e = 1} ^ {p_j^e \le n}f(p_j^e) \sum \limits _{x = 2, p_j^e | x} ^n f(\frac x {p_j^e}) [minp(\frac x {p_j^e}) \ge p_{j + 1} \ or\ \frac x {p_j^e} == 1 \ and \ x \ is \ not \ \ a \ prime]$

$= \sum \limits _{e = 1} ^{p_j^e \leq n} f(p_j^e) ([e \neq 1]+\sum \limits _{x = 2} ^{\lfloor \frac n {p_j^e} \rfloor} f(x) [minp(x) \ge p_{j + 1}])$

$= \sum \limits _{e = 1} ^{p_j^e \leq n} f(p_j^e) ([e \neq 1]+\sum \limits _{x = 2} ^{\lfloor \frac n {p_j^e} \rfloor} f(x) [x \in P \ or \ minp(x) \ge p_{j + 1}] - g(p_j))$

$= \sum \limits _{e = 1} ^{p_j^e \leq n} f(p_j^e) ([e \neq 1]+ S'(\lfloor \frac n {p_j^e} \rfloor, j + 1) - g(p_j))$

$= \sum \limits _{e = 2} ^{p_j^e \leq n} f(p_j^e) + \sum \limits _{e = 1} ^{p_j^e \leq n} f(p_j^e)(S'(\lfloor \frac n {p_j^e} \rfloor, j + 1) - g(p_j))$

$= \sum \limits _{e = 1} ^{p_j^{e + 1} \leq n} f(p_j^{e + 1}) + \sum \limits _{e = 1} ^{p_j^e \leq n} f(p_j^e)(S'(\lfloor \frac n {p_j^e} \rfloor, j + 1) - g(p_j))$

又当 $\lfloor \frac n {p_j^e} \rfloor \ge p_{j + 1} > p_j$ 即 $p_j^{e + 1} < n$ 时 $S'(\lfloor \frac n {p_j^e} \rfloor, j + 1) - g(p_j)$ 才不为 $0$ , 故

$= \sum \limits _{e = 1} ^{p_j^{e + 1} \leq n} f(p_j^{e + 1}) + \sum \limits _{e = 1} ^{p_j^{e + 1} < n} f(p_j^e)(S'(\lfloor \frac n {p_j^e} \rfloor, j + 1) - g(p_j))$

$= \sum \limits _{e = 1} ^{p_j^{e + 1} \leq n} ( f(p_j^e)(S'(\lfloor \frac n {p_j^e} \rfloor, j + 1) - g(p_j)) + f(p_j^{e + 1}))$ ，因为 $S'(p_j,j +1) - g(p_j)= 0$

$S'(n, j) = S'(n, j + 1) + \sum \limits _{e = 1} ^{p_j^{e + 1} \leq n} ( f(p_j^e)(S'(\lfloor \frac n {p_j^e} \rfloor, j + 1) - g(p_j)) + f(p_j^{e + 1}))$