学一遍忘一遍，忘一遍学一遍，生命就是在对抗熵增
这两个玩意儿都是用来求积性函数前缀和的（满足对应要求的非积性函数也可以求一下）
杜教筛
性质要求相对高一些
求 \(\sum_{i=1}^{n}f(i)\) ，需要找到 \(g(i),h(i)\)，满足 \(h=f*g\) 且 \(f,g\) 都可以快速求解前缀和
令 \(S(n)=\sum_{i=1}^{n}f(i)\)，推推式子：
则
递归求解即可，复杂度为 \(O(n^{\frac{3}{4}})\)
线性筛预处理前 \(n^{\frac{2}{3}}\) 个数后复杂度优化为 \(O(n^{\frac{2}{3}})\)
Min_25 筛
许多非积性函数也可以用这玩意求解，本质上是个优化埃氏筛的 DP
求 \(\sum_{i=1}^{n}f(i)\)
预处理不大于 \(\sqrt n\) 的质数，下用 \(p_i\) 表示第 \(i\) 个质数
先求质数部分的答案
质数部分求解时用一个或多个完全积性函数拟合求解的函数，只要满足质数部分答案相同即可
令该完全积性函数其为 \(f_0\)
要求 \(f_0\) 可以快速求前缀和以及某一个质数的幂对应的函数值
设 \(g(n,i)\) 表示前 \(n\) 个数中质数以及最小质因数大于 \(p_i\) 的合数的答案和（可以看作埃氏筛筛了前 \(i\) 个质数后的答案）
初值 \(g(n,0)\) 为 \(\sum^n_{i=1} f_0(i)\)
当 \(p_i > \sqrt n\) 时，显然不会再筛掉任何数了，\(g(n,i)=g(n,i-1)\)
当 \(p_i \le \sqrt n\) 时，转移为：
然后就可以求原函数的答案了
设 \(S(n,i)\) 为前 \(n\) 个数中最小质因数不小于于 \(p_i\) 的 \(f(x)\) 之和
有递推式：
答案为 \(S(n,1)+f(1)\)
复杂度为 \(O(\frac{n^{\frac{3}{4}}}{logn})\)，也有人说是 \(O(n^{1-\epsilon})\)，好像比杜教筛要优一点
完结散花