Min_25 筛 学习笔记
叫这个名字是因为这是 \(Min\_25\) 神犇发明的，主要用到的思想是对于质数和合数分开计算。
适用范围
对于一个积性函数 \(f(x)\) 求解:
\[\sum_{i=1}^{n}f(i) \]要求：\(f(p)\) ( \(p\) 为质数)是一个关于 \(p\) 的项数较少的多项式或可以快速求值，且 \(f(p^e)\) 可以快速求值
原理
首先考虑求解一个函数 \(G(n)=\sum_{i=1}^{n}[i \in prime]f(i)\)，即 \(n\) 以内所有质数的函数值。
考虑 \(dp\) 求解，定义 \(g(i,m)=\sum_{i=1}^{m}[i \in prime \; or \; minp(i)>p[j]]f'(i)\)
其中 \(minp(i)\) 表示 \(i\) 中最小质因子，\(p[i]\)表示第 \(i\) 个质数。
\(f'(i)\)是一个完全积性函数，满足当 \(i\) 为质数是取值与 \(f(i)\) 相同且前缀和可以快速求解
\(dp\) 边界 \(g(0,m)=\sum_{i=2}^{m}f'(i)\)
当 \(p[i]^2>m\) 时，\(m\) 内不存在最小质因子为 \(p[i]\) 的合数，不会造成贡献，所以 \(g(j,m)=g(j-1,m)\)
当 \(p[i]^2\le m\) 时：
\[g(i,m)=g(i-1,m)-f'(p[i])(g(i-1,\lfloor \frac{m}{p[i]} \rfloor )-\sum_{j=1}^{i-1}f'(j)) \]当 \(i-1\) 变成 \(i\) 时，所有最小质因子为 \(p[i]\) 的都被筛掉，因为 \(f'(i)\) 是完全积性函数,提出一个 \(f(p[i])\),剩下的要筛掉的就是最小质因子大于等于\(p[i]\) 的数，因为多算了 \(g(i-1,\lfloor \frac{m}{p[i]} \rfloor )\)里的质数所以要减掉
则 \(G(m)=g(x,m)\)，\(x\) 是小于等于 \(m\) 的质数个数
设 \(S(n,j)=\sum_{i=1}^{n}[minp(i) \ge p[j]]f(i)\)
质数的贡献为 \(G(n)-\sum_{i=1}{j-1}f(p[i])\)
合数的贡献可以枚举最小质因子和它的次数
\[ S(n,j)=G(n)-\sum_{i=1}^{j-1}f(p[i])+\sum_{i=j}^{p[i]^2\leq n}\sum_{e=1}^{p[i]^{e+1}\leq n}\Big(f(p[i]^e)S(\lfloor\frac{n}{p[i]^e}\rfloor,i+1)+f(p[i]^{e+1})\Big) \] 标签：lfloor,25,MIn,sum,笔记,因子,minp,质数 From： https://www.cnblogs.com/blue-tsg/p/17020220.html