原理

现在你有一个积性函数
f(1)=1
FP(p)
FPK(p,k)
首先要求的是前缀和，那就是f(质数)+f(合数)+f(1)，然后f(1)=1直接最后加上，算前面的时候直接忽略掉。
首先算质数（min25筛第一阶段）
为了能做必须先把f(x)搞成一堆完全积性函数的和一起筛，下面以其中一个f(x)为例
设G(n,j)为2-n中i(i是质数或者i的最小质因子>pj)的f(i)之和，f是积性函数中的FP函数
按j从小到大分层筛
相当于是埃氏筛用最小质因数pj筛
若pj>sqrt，G(n,j)=G(n,j-1)
若pj<=sqrt，则需要筛去最小质因子为pj的合数，于是把这个最小质因子拿出来，根据完全积性函数可得
G(n,j)=G(n,j-1)-pj*(G(n/pj,j-1)-sum_{i=1}^{j-1} f(pi)
这里减掉的是多余的质数的部分
然后注意一下初始状态
G(n,0)=sum{i=2}^n f(i)，把2-n所有数全按质数往FP函数里边代。
因为有好多不是质数的数全部按FP来算了，所以这个第一阶段在没有筛完sqrt以内所有质数的情况是，G(n,j)的值都是假的，没有什么意义的。
但是全部筛完之后，我们却能对于所有i<=n得到n/i以内质数的函数和，并且这些值全是正确的。那么我们忽略掉第二维记作G(n/i)（i=1...n），这是我们第一个阶段的总任务，也是核心所在！
递归计算答案（min25筛第二阶段）
接下来再把质数合数合起来算答案。
设S(n,j)表示2-n中的所有i(i的最小质因子>=pj)的f(i)之和，f就是原积性函数（注意与第一阶段所设状态的3处不同点）
然后我们把要算的数分三类
（1）质数
前缀和作个差：
S(n,j)+=G(n)-sum{i=1}^(j-1) f(pi)
G(n)已经筛出来了，而且值还是对的，那直接哪来用哇
（2）非纯合数
直接暴力！
枚举下最小质因子是谁：pk (k>=j)
枚举下最小质因子的指标：e (pk^{(e+1)<=n)（注意这里是pk}(e+1)，因为如果pk^e>n/e，那n就一定找不到别的>pk的质因子了）
那么S(n,j)+=S(n/pk^e,j+1)×FPK(pk,e)
这里把积性函数乘在外面，递归处理，也好理解。
（3）纯合数
更简单了
枚举下最小质因子是谁：pk (k>=j)
枚举下最小质因子的指数：e (2<=pk^e<=n)（注意从2开始，全是细节）
S(n,j)+=FPK(pk,e)
好理解。
欸这不就直接递归就做完了嘛，，，，
边界：
当n==1或者pj>n，S(n,j)=0。
那么直接调用S(n,1)，就能求得2-n中所有数字的f(i)之和，皆大欢喜。
别忘了还有个f(1)=1要加上。

实现

（1）表示状态
min25筛两个阶段都是类似DP的过程，需要记下标，N太大没发记。
由于发现过程中只涉及对N的除法，根据整除分块原理，一共只有O(sqrt)个点有值，拎出来即可。
（2）需要预处理的信息
sqrt以内的质数；
两个阶段都要求对sqrt以内的质数计算所给函数的前缀和，也要预处理出来。
G(n)的初值（把2-n全当做质数往FP里边代的结果，前文有提到）

复杂度与效率

复杂度玄学，不清楚是多少，网上说法不一，而且还不清楚第二阶段要不要记忆化。
大致情况是1s能跑1次10^11， 2次10^10，若干次10^9。

使用条件

（1）求积性函数前缀和
必须要FP是关于P的多项式，FPK容易用p,k算出
比如loj的模板就是FP=p-1,FPK=p xor k
（2）求关于最小质因子（最大真因数）、次大质因子的一些信息
前者在min25筛第一阶段筛G的过程中可以统计，因为每次是枚举最小质因子
后者在min25筛第二阶段筛S的（2）（3）部分可以统计，做法是钦定当前枚举的最小质因子是次大的然后算贡献。

一种递推实现的 min25 筛

这种方法可以求目标函数在根号 (dfrac{n}{i}) 个位置的前缀和，一般可以结合除法分块使用。
设 (F(n,j)) 表示 2~n 中，(minp(x)ge P_j) 或 x 是质数的函数和。
倒着递推：
若pj>sqrt，F(n,j)=F(n,j+1)
若pj<=sqrt，则需要加入最小质因子为pj的合数，枚举最小质因子重数，根据积性函数可得
F(n,j)+=(F(n/(pj^k),j+1)-sumpri(j)) * f(pj^k) (1<=k, pj^(k+1)<=n)
枚举形如 pj^k 的数
F(n,j)+=f(pj^k) (2<=k, pj^k<=n)
这么做大概就能算根号个位置的前缀和了，虽然看上去复杂度就不对。
~~只能跑10^10~~