学一遍忘一遍，忘一遍学一遍，生命就是在对抗熵增
这两个玩意儿都是用来求积性函数前缀和的（满足对应要求的非积性函数也可以求一下）
杜教筛
性质要求相对高一些
求 \(\sum_{i=1}^{n}f(i)\) ，需要找到 \(g(i),h(i)\)，满足 \(h=f*g\) 且 \(f,g\) 都可以快速求解前缀和
令 \(S(n)=\sum_{i=1}^{n}f(i)\)，推推式子：
\[\sum_{i=1}^{n}h(i)=\sum_{i=1}^{n}\sum_{d|i}f(\frac{i}{d})g(d)\\ =\sum_{d=1}^{n}g(d)S(\frac{n}{d}) \]则
\[g(1)S(n)=\sum^{n}_{i=1}h(i)-\sum^{n}_{d=1}g(d)S(\frac{n}{d}) \]递归求解即可，复杂度为 \(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\) 时，转移为：
\[g(n,i)=g(n,i-1)-f(p_i)(g(\frac{n}{p_i},i-1)-\sum_{j=1}^{i-1}f(p_j)) \]然后就可以求原函数的答案了
设 \(S(n,i)\) 为前 \(n\) 个数中最小质因数不小于于 \(p_i\) 的 \(f(x)\) 之和
有递推式：
\[S(n,i)=g(n,|P|)-\sum_{i=1}^{i-1}f(p_i)+\sum_{j=i}^{p_j^2 \le n}\sum_{e=1}^{p_j^e \le n}(f(p_j^e)S(\frac{n}{p_j^e},j+1)+f(p_j^{e+1})) \]答案为 \(S(n,1)+f(1)\)
复杂度为 \(O(\frac{n^{\frac{3}{4}}}{logn})\)，也有人说是 \(O(n^{1-\epsilon})\)，好像比杜教筛要优一点
完结散花
标签：25,frac,函数,Min,sum,求解,杜教,答案,质数 From： https://www.cnblogs.com/oier-moonlit/p/17610927.html