莫比乌斯函数与容斥原理

例题

没有周期性的字符串的计数

求所有由a~z组成的长度位n的字符串中,没有周期性的字符串的个数（$2<=n<=10^9$）。

• Time limit: 1 seconds

input

2

output

650

思路

对于这个题来说,用之前学过的知识来解决，首先想到的就是容斥原理，考虑含有周期性的串，然后用所有串的个数减去有周期性的串的个数，显然总的串的个数时$26^n$,对于有周期性的串，我们定义一个串X重复m 次的串为$X^m$,假设存在一个长度为d(d|n)的串，我们试着统计一下满足题目条件的周期为d的约数的串的个数，显然，任意长度为d的串重复$\frac{n}{d}$次构成的串的周期都是d的约数，这种串的个数就是$26^d$，那么我们记这种串的集合为$A_{d},且有|A_{d}|=26^d$，那么我们要求的是周期恰好为n的串的个数
$$res=|\bigcup_{d|n}A_{d}|$$
这是有一种解法就是容斥原理，这是显然的，我们考虑集合$A_{d}与集合A_{e}$，他们的交集恰好就是集合$A_{gcd(e,d)}$这时候如果我们如果通过枚举约数取值计算是可能的约数个数是$\prod {(e_{i}+1)}$,这个数虽然不是很大但是也有100多此时复杂度变成了$O(2^{100})$显然不能接受，那我们进一步利用刚才的性质，容斥原理中的某一项交集就可以写成
$$\bigcap_{i}A_{i}=A_{gcd(i,j,k,…)}$$
也就是说容斥原理的交集可以化简为$gcd的函数的形式$那么又可以知道这个这些数的最大公约数的个数最多只有$n的约数个$,那么我们可以将这些集合归并到一起，所以我们只需要对每个集合计算他被加减了多少次就可以，这时候我们的时间复杂度就只有O(n的约数个数),而这个被加减多少次的系数如何来算呢？$A_{i}$的系数只与$gcd(ki,…)$的个数与加减的次数有关，而ki又是n的约数,所以k的取值就是$\frac{n}{i}$的约数的个数。所以$A_{i}$的系数就是一个关于$\frac{n}{i}$的函数，而这个函数被人们总结成莫比乌斯函数$u$

重要的数论函数

• $\epsilon(n)=[n=1]$
• $1(n)=1$
• $Id(n)=n$
• $ u(n) = [max(e_{1},e_{2},…,e_{k})] (-1)^k $
• $\phi(n)=n\prod_{d|n}(1-\frac{1}{d})$
• $d(n)=\sum_{d|n}1$

狄利克雷卷积

定义

对于两个积性函数$f(n),g(n)$，定义他们的狄利克雷卷积为
$$f*g(x)=\sum_{d|n}f(d)g(\frac{n}{d})$$
狄利克雷卷积与数论函数共同构成群

• 结合律
• 封闭性
• 逆元
• 幺元

特殊的卷积

• $u*1(n)=\epsilon(n)$
• $\phi*1(n)=Id(n)$
• $Id*u(n)=\phi(n)$
• $d(n)=1*1(n)$
• $1(n)=u*d(n)$

莫比乌斯反演

约数反演

定义

$$F(n)=f * 1(n)=\sum_{d|n}f(d)$$
$$f(n)=u * F(n)=\sum_{d|n}F(d)u(\frac{n}{d})$$

证明

狄利克雷卷积可证

倍数反演

定义

$$F(n)=\sum_{n|d}f(d)=\sum_{i=1}f(id)$$
$$f(n)=\sum_{n|d}u(\frac{d}{n})F(d)$$

证明

$$\sum_{n|d}u(\frac{d}{n})F(d)=\sum_{i=1}u(i)F(in)$$
$$=\sum_{i=1}u(i)\sum_{j=1}f(ijn)$$
令$m=ij带入并整理得$
$$res=\sum_{m=1}f(mn)\sum_{i|m}u(i)$$
$$=\sum_{m=1}f(mn)(1*u)(m)$$
$$=\sum_{m=1}f(mn)\epsilon(m)=f(n)$$

一些积性数论函数的求和问题

例题

$$\sum_{i=1}^n\mu(i)$$

线性筛

有些积性函数他们本身计算起来十分复杂，但是在自变量为素数或者是素数的幂的时候容易计算，这时候我们利用积性函数的性质与算术基本定理可以通过筛法来进行计算
$$X=\prod_{i}P_{i}^{k_{i}}$$
$$f(P_{1}^{k_{1}}P_{2}^{k_{2}})=f(P_{1}^{k_{1}})f(P_{2}^{k_{2}})$$

时间复杂度证明

代码保证了计算的时候所有的数有且仅有一次被他的最小质因子所到达，这部分可以约为线性复杂度,除此之外，外循环会把每个数都遍历一次这部分也可以约为线性，所以整体复杂度是线性的。

代码

void init() {
    memset(vis, false, sizeof(vis));
    f[1] = f(1);
    tot = 0;
    for(int i = 2; i < maxn; i ++) {
        if(!vis[i]) {
            prime[tot ++] = i;
            f[i] = f(p);
        }
        for(int j = 0; j < tot; j ++) {
            if(i * prime[j] >= maxn) break;
            vis[i * prime[j]] = true; // x= i*p[j]
            if(i % prime[j] == 0) {
                f[i * prime[j]] = ; //x=p* k*p^k 不互质的情况且公因子仅有p质数
                break;
            }
            else {
                f[i * prime[j]] = ;//互质的情况
            }
        }
    }
}

小结

题目是求的积性函数的和，而并非是求得单个积性函数，这时候我们再使用线性筛法似乎不是那么的合适那利用找个性质是不是还有其他的方法呢？

杜教筛

传说是杜教发明的一种筛法。

目的

计算
$$\sum_{i=1}^nf(i)$$

引入

我们学习了反演(包括莫比乌斯反演，和二项式反演)，我们总会注意到，当有一些东西很难算或者不能直接算的时候我们总是将这个式子与另一种简单容易算的形式中去。
那么我们有没有学过一种东西可以把积性数论函数划归到另一种简单方式呢，当然就是我们的狄利克雷卷积
我们试图构造一个积性函数g(x)使得$g*f$是一个特殊的积性函数

推导

记
$$S(n)=\sum_{i=1}^nf(i)$$
有
$$\sum_{i=1}^nh(i)=\sum_{i=1}^nf*g(i)=\sum_{i=1}^n\sum_{d|i}g(d)f(\frac{i}{d})$$
$$=\sum_{d=1}^ng(d)\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}f(i)$$
$$=\sum_{i=1}^ng(d)S(\lfloor \frac{n}{d}\rfloor )$$
可以将右边式子的n=1的情况提出来
$$ \rightarrow g(1)S(n)=\sum_{i=1}^nh(i) -\sum_{d=2}^ng(d)S(\lfloor \frac{n}{d} \rfloor) $$
这时候我们尽量构造的g(i)可以简单计算 并且h(i)也尽量可以简单计算，这时候后面部分就可以数论分块+记忆化搜索来做，递归出口显然是就是预处理的块大小或者是记忆化搜索过的地方。

通常情况我们先用线性筛预处理一部分前缀和，通常这个前缀和的大小设置为$n^{\frac{2}{3}}$,

时间复杂度证明

网上瞎写的太多了，这个我觉得也比较玄学,，我这只做不严谨的证明
设计算出$S(n)$的复杂度为$T(n)$
首先有一点可以明确的是,累和只存在$\sqrt{n}个块,所以归并复杂度是\sqrt{n}$
$$T(n)=\sqrt{n}+\sum_{i=2}^{\sqrt{n}}(T(i)+T(\frac{n}{i}))$$
此处显然是以对数级别下降，那么主要时间复杂度都集中在归并上，此处可假定认为一层以下是高阶小量，则对一层展开，原始变为
$$T(n)=\sqrt{n}+\sum_{i=2}^{\sqrt{n}}\sqrt{i}+\sqrt{\frac{n}{i}}$$
$$\sqrt{n}>\sqrt{i}+\sqrt{\frac{n}{i}}>=2n^{\frac{1}{4}}$$
$$ \rightarrow n>T(n)>n^{\frac{3}{4}}$$
而为了解决展开一层的问题我们预处理了一部分前缀和设这部分的区间为[1,k],那么原式子可写成 $$T(n)=\sqrt{n}+\sum_{i=2}^{\frac{n}{k}}T(\frac{n}{i})$$
此时$$T(n)<=\sqrt{n}+\frac{n}{k}\sqrt{n}$$
而为了使总的时间复杂度最小问题变成
$$min_{k}(max(k,T(n)))$$
此时k选取$n^\frac{2}{3}$使得总时间复杂度为 $O(n^{\frac{2}{3}})$

数论分块

引入

求
$$res=\sum_{i=1}^n \lfloor \frac{n}{i} \rfloor$$

引理

1. $\lfloor \frac{n}{i} \rfloor$最多有$\lfloor 2\sqrt{n} \rfloor$种

2. 设$\lfloor \frac{n}{i} \rfloor 与 \lfloor \frac{n}{i’} \rfloor $相等，则i’的最大取值为$\lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor$

证明

1. 显然当$i<\sqrt{n} 时 \frac{n}{i}$ 最多$\sqrt{n}$项,而当$n>i>\sqrt{n}$时,$\frac{n}{i}<\sqrt{n}$ 此时$\lfloor \frac{n}{i} \rfloor$最多也是$\sqrt{n}$项，所以总和最多$\lfloor 2\sqrt{n} \rfloor$

2. 令$k=\lfloor \frac{n}{i} \rfloor$ 则存在特定的p，使得 $ki+p=n ,且1<=p<i $ 若存在d使得$\lfloor \frac{n}{i+d} \rfloor = k$, 此时则存在 $ p’>=0,使得k(i+d)+p’=n,$可以得到$p’=p-kd,$此时$d<= \lfloor \frac{p}{k} \rfloor$ 则i’的最大取值即为d的最大取值$$i_{max}^{‘} =i+d_{max}=i+\lfloor \frac{p}{k}\rfloor =i+\lfloor \frac{n\ mod\ i}{\lfloor \frac{n}{i} \rfloor } \rfloor=\lfloor i+ \frac{n- \lfloor \frac{n}{i}\rfloor i}{\lfloor \frac{n}{i} \rfloor}\rfloor =\lfloor \frac{n}{\frac{n}{i} } \rfloor$$

例题

tsy的数

求解
$$ \sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n\frac {φ(i)φ(j^2)φ(k^3)} {φ(i)φ(j)φ(k)}φ(gcd(i,j,k)) (mod \ 2^{30})$$
$T<=10^4,n<=10^7$

tsy 的数题解

根据欧拉函数计算公式可化简

$$\frac {φ(i)φ(j^2)φ(k^3)} {φ(i)φ(j)φ(k)}φ(gcd(i,j,k)) $$
为

$$ jk^2\phi(gcd(i,j,k))$$

关于这种式子的计算方法通常称为gcd反演
通常解法是令 $ d=gcd(i,j,k) $并提出含有gcd的项并进行倍数反演
对于该题则可以化简成

$$ \sum_{d=1}^n\phi(d)\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^njk^2[gcd(i,j,k)=d]$$

此时可以得
$$f(d) = \sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^n jk^2[gcd(i,j,k)=d]$$
$$=\sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^n jk^2[gcd(\frac{i}{d},\frac{j}{d},\frac{k}{d})=1]$$
$$=d^3\sum_{i=1}^\frac{n}{d} \sum_{j=1}^\frac{n}{d} \sum_{k=1}^\frac{n}{d} jk^2[gcd(i,j,k)=1]$$
令
$$F(d) =\sum_{d|x}f(x)$$
$$=\sum_{p=1}f(pd)$$
考虑何时$gcd(i,j,k)$为d的倍数
显然当$i,j,k$均为d的倍数时成立,并且对$gcd(i,j,k)$有且仅有一个p使得$pd$与之相等
$$F(d)=\sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^n \sum_{p=1}jk^2[gcd(i,j,k)=pd]$$
$$=d^3\sum_{i=1}^\frac{n}{d} \sum_{j=1}^\frac{n}{d} \sum_{k=1}^\frac{n}{d} jk^2$$

令
$$S(d)=\sum_{i=1}^d \sum_{j=1}^d \sum_{k=1}^djk^2$$
$$=d\sum_{k=1}^d\sum_{j=1}^djk^2$$
$$=d\sum_{k=1}^dk^2\frac{j(j+1)}{2}$$
则
$$F(d)=d^3S(\frac{n}{d})$$
$$f(x) =\sum_{x|d}\mu(\frac{d}{x})F(d)$$
$$=\sum_{i=1}\mu(i)F(ix)$$
$$res=\sum_{d=1}^n\phi(d)f(d)$$
$$=\sum_{d=1}^n\phi(d)\sum_{i=1}^\frac{n}{d}\mu(i)(id)^3S(\frac{n}{id})$$
$$=\sum_{d=1}^n\phi(d)\sum_{i=1}^\frac{n}{d}(id)^3\mu(i)\frac{n}{id}S_{2}(\frac{n}{id})$$
显然这个式子不太好计算由于题目的组数太多，需要找到一种简单计算的方法,由此引入数论分块
此时令$T=id$并提出来
$$res=\sum_{T=1}^nT^3\frac{n}{T}S_{2}(\frac{n}{T})\sum_{d|T}\phi(d)\mu(\frac{T}{d})$$
$$=\sum_{T=1}^nT^3\phi\mu(T)\frac{n}{T}S_{2}(\frac{n}{T})$$
这时候我们可以预处理$T^3\phi\mu(T)$的前缀和配合数论分块计算整个式子
复杂度，预处理复杂度$O(n)$单组查询$O(\sqrt{n}）$

问题:可不可以更快？

洲阁筛

问题

$$\sum_{i=1}^n F(i)$$

引入

我们在学习线性筛的时候遇到了一个问题，我们是通过枚举质数来计算的的积性函数的每一项，然后利用每一步的结果来求前缀和做的，并非是把前缀和看作一个整体，而学习杜教筛的时候是把前缀和看作了一个整体了已经，但是不具备普适性，那么存不存在一种方法在把前缀和看作一个整体的基础上且要求不是很高的算法呢？比如只要求质数和幂次的时候是一个低阶多项式

思想

再来思考积性函数的性质，发现有一个至关重要的东西一直在引导我们不断的优化，就是质数，只要有函数在定义域为质数时的定义，有质数幂次的定义，再加积性函数的性质，就可以拓展到整个定义域，那我们有没有一种方法可以做到并不需要对每个质数单独考虑，而是把某些质数整体考虑的方法呢？
在此我们引入一种分类方法，把质数分为两类，一类是小于等于$\sqrt{n}$的质数,另一类是大于$\sqrt{n}$的质数。

思考为什么这样分？

对于1~n的每一个数来说，最多有一个大于$\sqrt{n}$的质因子。根据是否有大于$\sqrt{n}$
我们可以通过把质数分类进而把所有的数分成两类，一类是包含大于$\sqrt{n}$的质因子的数，另一类是不包含$\sqrt{n}$质因子的数，对于含有大于$\sqrt{n}$质因子的数枚举小于$\sqrt{n}$的部分，对于不含有大于$\sqrt{n}$质因子的数，可以通过枚举小于等于$\sqrt{n}$的质数来筛掉。

推导

$$\sum_{i=1}^nF(i)=\sum_{i=1}^{\sqrt{n}}F(i)(\sum_{p>\sqrt{n}}^{\lfloor \frac{n}{i}\rfloor} F(p)[p为质数])+\sum_{i=1}^nF(i)[i无大于\sqrt{n}的质因子]$$

算法

这里从式子上来看，我们的算法可以分为三个部分。

1. 计算$$F(i)$$
2. 计算$$\sum_{p>\sqrt{n}}^{\lfloor \frac{n}{i}\rfloor} F(p)[p为质数]$$
3. 计算$$\sum_{i=1}^nF(i)[i无大于\sqrt{n}的质因子]$$

第一部分

线性筛直接解决

第二部分

$$\sum_{p>\sqrt{n}}^{\lfloor \frac{n}{i}\rfloor} F(p)[p为质数]$$
这个问题换一种问法就变成了对于区间$[1,m]$,求所有大于$\sqrt{n}$的质数的$f(p)$之和。
此时如果$f(p)$是一个多项式就存在一种化简方法(如果不是多项式也可能存在化简方法，如果真的遇到这样的问题那应该也不是一时半会儿能想出来的，想出来就相当于提出了一种新的方法)
如果$f(p)$是一个多项式的话我们可以简单的按幂次来归类，最后合并，那么现在的问题变成

$$\sum_{p>\sqrt{n}}^{m} p^k\ [p为质数]$$

此时我们假设小于等于$\sqrt{n}$的素数从小到大，分别是$P_{1},P_{2},…,P_{q}$。设
$$f(i,j)=\sum_{k=1}^jF(k)\ [k的最小质因子大于P_{i}]$$
,显然边界有$f(0,j)=\sum_{i=1}^jp^k$,而对于我们的结果就是$f(q,j)$(这里有一个点值得思考为什么是一样的，显然因为大于$\sqrt{n}$的质因子最多有一个，那么小于$\sqrt{n}$的质因子，剩下的就只可能是质数),现在考虑递推，如何从前$i-1$个质数推到前$i$个质数，其实这部分也不复杂，用前$i-1$的结果减去与前$i-1$个质数互质但与第i个质数不互质的数即可，此时可以利用前面的结果，假设存在一个x与前面的$i-1$个质数互质，则$xp_{i}$必定符合，又有$xp_{i}<=j$则有$x<=\lfloor \frac{j}{p_{i}} \rfloor$所以可以写出递推式
$$f(i,j)=f(i-1,j)-p_{i}^kf(i-1,\lfloor \frac{j}{p_{i}} \rfloor)$$
而我们要计算的是$f(q,j)$
考虑这个式子计算复杂度，如果是地推的话则一定会把状态空间填满，这时候来讲q为小于$\sqrt{n}$的约数的个数大约为$\frac{\sqrt{n}}{ln\ \sqrt{n}}$,而j的取值通过刚才的数论分块的知识可以知道有$2\sqrt{n}$种，乘起来还是n的状态空间，
接下来的部分就是最核心的优化部分了

有一个性质我们没有注意到，那就是如果$P_{i}>j$的时候意味着除了1以外的数都被筛掉了，显然只要j不为零的时候，$f(i,j)=1$。那么如何利用这个性质呢？
如果$P_{i-1}>\lfloor \frac{j}{p_{i}} \rfloor$ 则此时的为函数值为1，由于有向下取整的缘故，我们将条件放宽一些因为$P_{i}-P_{i-1}>=1>\frac{j}{p_{i}}-\lfloor \frac{j}{p_{i}} \rfloor$,此时条件可以放宽到$P_{i}>\frac{j}{p_{i}}$,则此时变为$P_{i}^2>j$
所以此时当$j<P_{i}^2$时$f(i,j)=f(i-1,j)-p_{i}^k$,所以当i比较小的时候仔细去算，当i达到一定大小的时候直接算一个前缀和就可以了。
而当$P_{i}>j$的时候显然$\lfloor \frac{j}{p_{i}} \rfloor$为0此时无需计算$f(i,j)=f(i-1,j)$
综上

• 当$P_{i}^2<j $ 时 直接计算
• 当$j<P_{i}^2<j ^2 $ 时 计算$p^k$的前缀和
• 当$P_{i}>j$时 直接用结果

递推式只与i-1有关，所以直接用滚动数组就可以计算，具体实现也比较简单

• 当$P_{i}^2<j $时 直接$f(j)=f(j)-P_{i}^kf(\lfloor \frac{j}{p_{i}} \rfloor)$
• 当$P_{i}^2>=j $时 如果计算某个特定的$f(i_{1},j)$只需要加上保留的轮数$i_{0}$与$min(i_{1},primecnt_{j})$差值部分的前缀和

时间复杂度
对于函数$f(i,j)$，每个j所对应的i的枚举范围时$\frac{\sqrt{j}}{ln\ j}$,而j的范围最多是$\sqrt{n}$个
$$\sum_{i=1}^{\sqrt{n}} \frac{\sqrt{\frac{n}{i}}}{ln\ \frac{n}{i}}<=\frac{n^{\frac{3}{4}}}{ln\ n}$$

到现在为止我们的公式已经变成了这个，
$$\sum_{i=1}^nF(i)=\sum_{i=1}^{\sqrt{n}}F(i)f(q,\lfloor \frac{n}{i} \rfloor )+\sum_{i=1}^nF(i)[i无大于\sqrt{n}的质因子]$$

第三部分

求
$$ \sum_{i=1}^n f(i)\ [i无大于\sqrt{n}的质因子]$$

这一部分依然采用地推的方式来做，但是这次试着从后往前地推。依然规定小于$\sqrt{n}$的质因子为$P_{1},P_{2}…,P_{q}$
设$g(i,j)$为$[1,j]$的区间内，只含有质因子$P_{i},…P_{q}$的数的函数值之和，显然有上边界
$$g(q+1,j)=1$$
而我们要求的为$g(1,n)$,考虑由i+1到i的地推，那么可以有下面的递推式：
$$g(i,j)=g(i+1,j)+\sum_{c=1}^{P_{i}^c<j} F(P_{i}^c)g(i+1,\lfloor \frac{j}{P_{i}^c}\rfloor )$$
这个递推式的意义就是，当新加一个质因子时，只需要枚举质因子的幂次即可。并且保证在区间之内
找个递推式直接地推也是线性级别的，依然需要优化

和第二部分类似，同样考虑$g(i,j)$的特殊情况，如果有

• $P_{i}>j$ 时，则显然$g(i,j)=1$这时候显然不需要计算
• $P_{i+1}>\lfloor \frac{j}{P_{i}}\rfloor$时,这个条件与上面的条件相同同理可以放宽到$P_{i}^2>j>=P_{i}$此时$g(i+1,\lfloor \frac{j}{P_{i}}\rfloor )=1$而此时的c>1时无意义。

这个递推过程显然也可以用滚动数组来做，$i$从大到小,$j$从大到小
所以算法可以归结如下

• $j>=P_{i}^2$时，老实计算
• $P_{i}^2>j>=P_{i}$时利用已经计算好的前缀和
• $P_{i}>j$ 无需计算

时间复杂度分析
这个分段和第二部分分段基本相同，所以时间复杂度也相同时$$O(\frac{n^{\frac{3}{4}}}{ln\ n})$$

综上
原式子变为
$$\sum_{i=1}^nF(i)=\sum_{i=1}^nF(i)f(q,\lfloor \frac{n}{i}\rfloor)+g(1,n)$$

总时间复杂度

$$O(\frac{n^{\frac{3}{4}}}{ln\ n})$$

min25筛

引入

思考洲阁筛的分类方法，根据是否含有大于$\sqrt{n}$的质因子来进行分类，这思路非常具有启发性，而我们在计算的时候发现洲阁筛的第一部分和第二部分的归并还是较为繁琐，是否可以存在其他的分类方式让这个过程看起来更简单一些呢？这里就是min25筛提出来的一种根据质数和合数来进行分类。其思想是和埃氏筛的相同的枚举最小质因子的方法。

思考还有哪些性质和最小质因子有关？

• 对于区间$[1,n]$以内的数，如果最小质因子大于$\sqrt{n}$那么这个数必定就是质数
• 对于区间$[1,n]$以内的数，如果他是合数，那么这个数一定有小于等于$\sqrt{n}$的质因子

推导

这里我们依然将小于等于$\sqrt{n}$的质数记为$P_{1},P_{2},…,P_{q}$，并且利用最小质因子的性质，引入一个新的记号$S(n,j)$有
$$S(n,j)=\sum_{i=2}^nF(i)[i的最小质因子大于等于P_{j}]$$
为什么这么引入?
网上很多资料都没有提到这个问题，其实答案其实也挺明显的，方便递归啊，我从头开始枚举质因子就能写出相关的递归式。
所以显然我们的最终答案就是$res=S(n,1)+F(1)$
那么这个S如何计算呢？
而根据我们刚才的性质就可以推出两点:

• 对于所有合数我们都可以通过枚举小于$\sqrt{n}$的最小质因子来做
• 然后再加上质数部分即可

然后出现了一个新的问题，质数怎么算？想一想我们洲阁筛的第二部分是怎么做的？我们引入了一个新的函数$f(i,j)$表示的是最小质因子大于$P_{j}$的数之和，然后我们就成功的枚举了大于$\sqrt{n}$的部分的质数，在这里我们显然也可以用这个方法，而且这个方法也不慢，不过现在网上所流行的min25筛用的方法都是另一种，不过其实也很类似，既然第一种方法已经讲过了我们就提一下另外一种方法。
此处引入$f(i,j)$有
$$f(i,j)=\sum_{k=2}^jF(k)[k是质数或者k的最小质因子大于P_{i}]$$
此处依然可以写递推式
$$f(i,j)=\begin{cases}
f(i-1,j)-F(P_{i})\left( f(i-1,\lfloor \frac{j}{P_{i}}\rfloor)-f(i-1,P_{i}-1) \right) & j>=P_{i}^2 \
f(i-1,j) & 1<=j<P_{i}^2
\end{cases}$$

和洲阁筛的递推式类似，括号里面是减去的不满足质数，这时候括号里的内容就是最小质因子大于等于$P_{i}$的数，由三段换成了两段，是因为这里的定义是从2开始的，而洲阁筛那是从1开始的所以会出现这个问题。详情见上文洲阁筛
这时候质数部分就可以求解了，显然质数的和就是$f(n,q)$这时候就可以写递推式

$$S(n,j)=f(n,q)-\sum_{i=1}^{j-1}F(i)+\sum_{k \ge j}^{q}\left(\sum_{e=1}^{P_{k}^e \le n }F(P_{k}^e)S(\lfloor \frac{n}{P_{k}^e}\rfloor ,k+1)+\sum_{e=2}^{P_{k}^e \le n}F(P_{k}^{e})\right) $$

这个递推式其实也很好理解，枚举小于等于$\sqrt{n}$的最小质因子来计算合数的部分。递归出口$S(i,q+1)$

时间复杂度

首先对于$f(n,1)$的计算由洲阁筛的证明可以知道时间复杂度是$O(\frac{n^{\frac{3}{4}}}{ln\ n})$
而在递归式中我们设$S(n)$的计算时间为$T(n)$ 有
考虑$S(i,j)$的i的所有可能取值最多为n的约数次，而j的取值为$\frac{\sqrt{n}}{ln\ n}$次,而约数个数级别约为$n^{\frac{1}{4}}$,所以最终的复杂度为
$$O(n^{\frac{1}{4}}*\frac{\sqrt{n}}{ln\ n})\approx O(\frac{n^{\frac{3}{4}}}{ln\ n})$$

另一种带有特殊系数的前缀和筛法

引入

求
$$\sum_{i=1}^nF(in)$$
其中$m,n$都巨大，大概都超过$10^9$，但是这个系数n有一个特点，比如他的质因子的幂次均为1

其中$F(x)$为积性函数给出$F(P^k)$的定义,并且有递推式$F(P^{k+1})=H(P)F(P^{k})+b,k \ge 1$
首先拿到这个题的时候，我们回想一下用之前的知识能否解决呢？思考如果构造新的函数$g(x)=F(xn)$
$$g(P_{1}P_{2})=F(P_{1}P_{2}n)$$
如果这个$g(x)$也满足是一个积性函数，并且有$g(P^k)$是一个多项式，那么就可以用min25筛来做了。
但是似乎用min25筛来做过于暴力了忽略了一些重要的性质，而且构造的这个个函数还不一定是积性函数。
我们从他的质因子幂次均为1中能不能推出一些东西呢？

推导

这次我们引入新的记号$S(k,n)$表示原式
其中$P_{i}$为k从小到大排序的第$i$个质因子,这时候可以利用是否包含$P_{i}$依然是把整个区间$[1,n]$分为了两类，并且这两类因为存在递推关系，还可以提出来缩小范围
$$S(k,n)=\sum_{i=1}^nF(ki)=\sum_{P_{1}| \ i}F(ki) + \sum_{P_{1} \nmid\ i}F(ki)$$
$$=H(P_{1})\sum_{P_{1}|i}F(\frac{k}{P_{1}}i)+ F(P_{1})\sum_{P_{1} \nmid\ i}F(\frac{k}{P_{1}}i)$$
$$=F(P_{1})S(\frac{k}{P_{1}},n)+\left( H(P_{1})-F(P_{1}) \right)S(k,\lfloor \frac{n}{P_{1}} \rfloor)$$
这时候就可以通过递归将原式子化为小规模问题进行递归，递归出口显然$S(1,n)$为前缀和，这时候再思考用杜教筛，min25筛去求解

复杂度分析

如果采用这种递归筛法，显然$S(i,j)$中i的取值范围就是k的质因子个数一般不会超过20个，而j也是k的质因子个数，所以递归复杂度大概也就是$200$左右,而计算前缀和的复杂度是问题的关键，这部分可以采用杜教筛或者min25筛来做，总复杂的就是$$O(200T_{前缀和})$$

例题

$$\sum_{i=1}^nu(ik)$$