这篇居然是洲阁筛的学习笔记？？？
使用目标：求积性函数前缀和。
使用前提：
$1$、$F(x^k)$在$x\in{prime}$时能够快速计算。
$2$、能够构造出某若干个完全积性函数$G(p)$使得在$x\in{prime}$时$F(p)=\sum G(p)$，并且任意的$G(p)$能够快速求和，一个简单的例子就是$F(p)$为一个多项式，$G(p)$就是一个单项式。
part0
根据函数的积性，可以得到：
这里很容易想到根据$\lfloor\frac{n}{x}\rfloor$的取值分成$\sqrt{n}$段，设$y$为枚举的$\lfloor\frac{n}{x}\rfloor$的值，那么要分别计算下面两个部分：
part1 计算$G(p)$
设不超过$\sqrt{n}$的质数一共有$m$个，升序排列为$p_1…p_m$。
根据埃氏筛的逻辑，只需要将小于等于$\sqrt{n}$的质数及其倍数全部筛掉那么剩下来的就是大于等于$\sqrt{n}$的所有质数。
在这里，构造出来的$G(p)$是某个完全积性函数，因此也可以采用类似的方式逐个筛掉小于等于$\sqrt{n}$质数的贡献。
设$g[i][j]$为$[1,j]$范围内与前$i$个质数互质的所有的数的$G(p)$之和，$g[0][j]$的答案需要预先求出，这也就是为什么最上面要求了$G(p)$能够快速求和。
然后枚举$i$，考虑$[1,j]$内有多少含有$p_i$质因子的数与前$i-1$个数互质，设$l=\lfloor\frac{j}{p_i}\rfloor$，有如下递推式：
考虑一下这么做的意义，$[1,j]$内还能与$p_i$不互质的数字一定都在$[1,l]$之间这一堆的数再乘上$G(p_i)$就是$p_i$的所有倍数，即所有与$p_i$不互质的部分的贡献了，减去即可。
这样递推得到的$g[m][j]-G(1)$就是$[1,j]$内所有大于$\sqrt{n}$的质数的$G(p)$之和。
观察到，计算$g[m][n]$的过程中需要的第二维状态就是所有的$\lfloor\frac{n}{x}\rfloor$的取值，也只有$O(\sqrt{n})$种。
朴素实现的话，需要一次枚举质数$p_i$，并且对每一个状态进行计算。
考虑每个$\lfloor\frac{n}{x}\rfloor$有多少质数需要转移，其中$\lfloor\frac{n}{x}\rfloor>\sqrt{n}$的部分需要转移$\sqrt{n}$范围内所有质数。
这个复杂度过高，考虑进行优化：
当$p_{i+1}>j$时，一定有$g[i][j]=G(1)$，因为这时所有可能的数字均已被筛去。
那么，当$p_i^2>j\geq p_i$时，即$l=\lfloor\frac{j}{p_i}\rfloor<p_i$时：
因此可以省去$p_i^2>j$时的计算部分，因为在$p_i^2>j$之后所有质数的贡献都相同可以一起计算。那么可以考虑对于每个$j$都记录一下最后一次转移的$i$的值，在调用$g[i][j]$的位置的时候就可以直接将这一部分的质数的贡献计入。
以下，$last[j]$表示$j$最后一次转移时的$i$的值。
令$S_k=\sum_{i=1}^{k}G(p_i)$，这个东西是可以预处理出来的。
这个形式是相当方便的，因为在转移完全的时候，$last[l]=i-1$，那么就相当于这个优化不生效，而原来的递推关系式依旧是成立的，每次对于$i$只需要枚举$\geq p_i^2$的$j$并且更新对应的$last[j]$就可以了。
这样对于每一组$\lfloor\frac{n}{x}\rfloor$只需要转移不超过$\sqrt{\lfloor\frac{n}{x}\rfloor}$的质数，那么复杂度就可以记作：
至于怎么算的…….去问隔壁数学组吧。
part2 计算$F(x)$
将不超过$\sqrt{n}$的质数降序排列为$p_1….p_m$。
设 $f[i][j]$表示只包含前$i$种质因子，且$x\leq j$的$F(x)$之和，易知$f[0][j]=1$。下设$l_c=\lfloor\frac{j}{p_i^c}\rfloor$
这是一个比较显然的转移方程，最后枚举了$p_i$的指数，再利用函数的积性将前$p_i$个质数组成的答案拿过来进行合并。
第一维的状态数为$O(\frac{\sqrt{n}}{log\ n})$(质数数量)，第二维的状态数为$O(\sqrt{n})$，那么直接计算的复杂度就至少不会低于$O(\frac{n}{log\ n})$
在前一部分通过发现$p_i^2>j$时的转移有规律而将复杂度大幅度减少，这启发我们再用类似的方法优化。
当$p_i^2>j$时，设$l=\lfloor\frac{j}{p_i}\rfloor$:
注意到因为$p_i>l=\lfloor\frac{j}{p_i}\rfloor$，而$p_i$又是降序枚举的，所以根据定义一定有$f[i-1][l]=1$。
那么依旧可以省去$p_i^2>j$这部分的计算，记$last[j]$表示$j$位置最后一次转移时的$i$的值，那么：
同理，线性筛预处理出$S_k=\sum_{i=1}^kF(p_k)$
那么对于每一个第二维状态$\lfloor\frac{n}{x}\rfloor$，都只有大于$\sqrt{\lfloor\frac{n}{x}\rfloor}$的质数需要转移，这样子就和$part1$的复杂度几乎一致了，经过证明也是$O(\frac{n^{\frac{3}{4}}}{log\ n})$。
总结
可以发现，州阁筛的核心思想如下：
$1$、将数分成最大质因子不大于$\sqrt{n}$与大于$\sqrt{n}$的质数两部分，再利用函数的积性合并答案。
$2$、对于大于$\sqrt{n}$的部分，构造某个完全积性函数$G(p)$，枚举小于$\sqrt{n}$的质数，将合数的贡献从能够快速求出的$G(p)$之和中逐步筛去。
$3$、对于最大质因子小于$\sqrt{n}$的部分，枚举质数并再利用函数的积性将答案重新合并。
$4$、通过某些方式（改变枚举质数的顺序等），将$p_i^2>j$的相同系数转移部分省掉，并且通过预处理相同系数转移的前缀和数组节省复杂度。
$5$、如果有心的话，就会发现，州阁筛本质上就是按照某种方式将$[1,n]$的所有数都按某种顺序进行了质因数分解，因此可以完成大部分筛法的功能（因为几乎所有数论函数都可以通过质因数分解求出单点的取值）.
实现细节
$1$、数组不能直接开，要使用滚动数组，而不转移的部分不进行滚动。
$2$、因为二维数组的第二维状态量很小但是数值很大，应该使用$hash$表来储存。这里推荐使用手写$hash$表。因为大于$\sqrt{n}$的状态都可以与一个小于$\sqrt{n}$的数一一对应，那么直接一除就可以得到$hash$表中对应的下标。
Update
计算$f[][]$的时候如果不使用滚动数组+$Hash$递推，而是采用倒过来搜索的方式（不记忆化）就是$Min_25$筛了？
这就是$Min_25$筛好写、复杂度玄学、常数小的原因？？？