dgf
dgf定义为$F(z)=\sum\limits_i\frac{f(i)}{i^z}$，容易知道它的乘法就是狄利克雷卷积。平时我们经常用$\mathbf{1}=\zeta$来表示其它的dgf，比如$\mathrm{id}_k=\zeta(z-k),\mathrm{\mu}=\frac{1}{\zeta},\varphi=\frac{\zeta(z-1)}{\zeta(z)},\mu^{\cdot 2}=\frac{\zeta(z)}{\zeta(2z)},2^{\omega(n)}=\frac{\zeta^2(z)}{\zeta(2z)}$。
因此我们默认乘法是狄利克雷卷积。$f\cdot g$表示点乘，$f^{\cdot 5}$表示点五次方。
当我在数论函数和dgf之间用等号的时候，说的是该dgf是该数论函数的dgf。
显然任意dgf可以线性地加减，$O(n\log n)$地乘除。
贝尔级数
对于积性函数，我们可以考虑一个素数$p$对应的贝尔级数$\sum\limits_i f(p^i)z^i$。这些计算很多在你算ogf的时候已经很熟练了。
往各素数对应的贝尔级数代入$\frac{1}{p^z}$并乘起来就得到dgf。
基本和组
前缀和在各$\lfloor\frac{n}{k}\rfloor$处的值。有时我用 基本和组处 指各$\lfloor\frac{n}{k}\rfloor$，比如 $f$的基本和组 指的是 $S_f$在基本和组处的值。
很多时候我们需要存基本和组。此时常常选择根号分治，不超过根号的直接存，超过根号的存到另一个数组的$\frac{n}{k}$位置上。
线性积性函数狄利克雷卷积
爆力卷出素数幂处的值，这里相当于一个多项式乘法，然后线筛所有的值，复杂度就是线性。也就是$\sum\limits_{p\leq n}\log_p^2 n=O(n)$。
因为相当于一个多项式乘法，做除法 ln exp啥的也都是可以的。
$O(n\log\log n)$给任意函数卷一个积性函数
积性函数就是$\prod\limits_p(1+\sum\limits_i \frac{a_{p,i}}{p^{iz}})$这样的东西嘛。那么直接对每个素数分开卷，$1$那一项是不用动的，剩下的，贡献只有$n(\frac{1}{p}+\frac{1}{p^2}+…)=\frac{n}{p-1}=O(\frac{n}{p})$次，所以复杂度是$O(n\log\log n)$。
$\ln,\exp$
$\ln(1-z)=-\sum\limits_i\frac{z^i}{i},\exp z=\sum\limits_i\frac{z^i}{i!}$。首先可以不停爆力卷自己做到$O(n\log^2 n)$，因为一个数卷$\log$次就没了。
还是考虑$\ln F=\int\frac{F^\prime}{F}$。但是这里导数跟多项式不太一样啊，$(\frac{1}{n^z})^\prime=-\frac{\ln n}{n^z}$，而$\ln n$是啥呢。不过我们知道积分之后这个$\ln n$就消掉了。可以证明这里用一个除了$1$处都不为$0$的完全加性函数代替$\ln n$，比如$\Omega$，就可以算出正确的dgf $\ln$。
由于狄利克雷卷积很容易在线，$\exp$直接对着微分方程做即可。这样我们就会$O(n\log n)$的$\ln,\exp$了。但是有小朋友说这个$\exp$没有懂，我们考虑$(\exp F)^\prime=F^\prime\exp F$，于是计算$F^\prime\exp F$时就可以知道$(\exp F)^\prime$的某一项应取何值。和爆力的多项式$\exp$是一样的。这里用$\Omega$代替$\ln$也是正确的。
对于积性函数，可以对各素数分别做，$\ln$的时候跟非素数幂压根没有关系，$\exp$的时候再线筛出所有值，复杂度是线性。
轮子筛
可以在$O(\frac{n}{\log\log n})$内筛出前$n$个素数。
考虑我们取前$k$个素数，设它们的乘积是$L$，那么$n$和$n+L$是否被这$k$个素数整除的情况是相同的，所以我们考虑把$kL+1,…,(k+1)L$作为一段处理，这看起来就像用一个长$L$的轮子滚过数轴。
取最大的$k$使得$L\leq\sqrt{n}$，素数定理分析一下可以知道$k$是$\Theta(\log n)$的。
mertens定理指出这$L$个数里面有$O(\frac{L}{\log k})$个数不被前$k$个素数整除，也就是说我们一共有$O(\frac{n}{\log k})=O(\frac{n}{\log\log n})$个数还没被筛掉。
这些还没筛掉的数就是所有最小素因数在$k+1$个及以后的素数。显然这些数的乘除是封闭的。我们只用$k+1$及以后的素数，在这些数里面跑一个线筛，复杂度就是$O(\frac{n}{\log\log n})$。在word-ram下直接压位复杂度就是对的。
基本和组的狄利克雷乘除
现在我们知道$g,h$的基本和组，要求$f=gh$的基本和组。
\[S_f(n)=\sum_{i=1}^n\sum_{d\mid i}g(d)h(\frac{i}{d})=\sum_dg(d)\sum_{i=1}^\frac{n}{d}h(i)=\sum_dg(d)S_h(\lfloor\frac{n}{d}\rfloor)\]根号分治，对于$K$以内直接线筛，超过的按这个做，显然这里我们整除分块的时候也只需要$g$的基本和组，如果$K=\Omega(\sqrt{n})$，复杂度积一下就是$O(\frac{n}{\sqrt{K}})$，取$K=\Theta(n^\frac{2}{3})$时复杂度是$O(n^\frac{2}{3})$。如果不是积性函数，就不能线性地卷，需要调整一下。
对于除法，如果我们有$f=\frac{h}{g}$，那么也就是$h=fg$，此时我们考虑$S_h$是啥
\[\begin{aligned} S_h(n)&=\sum_dg(d)S_f(\lfloor\frac{n}{d}\rfloor)\\ &=S_f(n)+\sum_{d>1}g(d)S_f(\lfloor\frac{n}{d}\rfloor) \end{aligned}\]从小到大递推，那个$\sum$就是已知的了。复杂度是相同的。
比如它可以处理$\varphi=\frac{\zeta(z-1)}{\zeta(z)}=\frac{\mathrm{id}_1}{\mathrm{id}_0}$。这被称为 杜教筛。
$\mu^{\cdot 2}$，或者说$\zeta(2z)$和完全平方数的整除分块
可以注意到$\mu^{\cdot 2}$的dgf是$\frac{\zeta(z)}{\zeta(2z)}$。考虑$\frac{1}{\zeta(2z)}$是个什么东西，它就是$\zeta(2z)=\sum\limits_i\frac{1}{(i^2)^z}$的逆，$\zeta(2z)$就是完全平方数的dgf，容易算出$\frac{1}{\zeta(2z)}=\prod\limits_p(1-\frac{1}{p^{2z}})$，它是$z^2$的函数所以只在完全平方数处有值。所以我们可以在完全平方数上整除分块一下做到$O(\sqrt{n})-O(n^\frac{1}{3})$。
具体地，还是考虑
\[S_f(n)=\sum_dg(d)S_h(\lfloor\frac{n}{d}\rfloor)\]这里也就是$g$只在完全平方数处有值。改写为
\[S_f(n)=\sum_dg(d^2)S_h(\lfloor\frac{n}{d^2}\rfloor)\]于是可以使用完全平方数上的整除分块。$\lfloor\frac{n}{d^2}\rfloor$的取值只有$O(n^\frac{1}{3})$种，对$d$和$n^\frac{1}{3}$的大小关系讨论就可以说明这件事。考虑如何实现，给一个$l$，要求出最大的$r$满足$k=\lfloor\frac{n}{l^2}\rfloor=\lfloor\frac{n}{r^2}\rfloor$，那么也就是$\frac{n}{r^2}-1<k\leq\frac{n}{r^2}$，也就是$\frac{n}{k+1}<r^2\leq\frac{n}{k}$，最大的$r$就是$\left\lfloor\sqrt{\frac{n}{k}}\right\rfloor=\left\lfloor\sqrt{\frac{n}{\lfloor\frac{n}{l^2}\rfloor}}\right\rfloor$。
注意到不需要枚举所有的完全平方数，我们其实是要算$\lfloor\sqrt{n}\rfloor$的基本和组处的$\frac{1}{\zeta(z)}=\mu$的前缀和，使用杜教筛，复杂度就是$O(n^\frac{1}{3})$了。这个板子出现在蓝桥杯2023省赛A组的J。
powerful numbers
现在要求积性函数$f$的前缀和$S_f(n)$，我们找一个$g$使得它积性，并且在素数处和$f$取值相同。那么我们知道$\frac{f}{g}$也是积性的，这里除法是狄利克雷卷积的逆，并且它在素数处全$0$，因此它仅在每个素数的次数都$\geq 2$的数处非$0$，这些数称为powerful numbers。每个powerful number都可以表示成$a^2b^3$的形式，积分可知powerful numbers只有$O(\sqrt{n})$个。通过拆式子我们可以得到，只要求出$\frac{f}{g}$在powerful numberes处的值和$g$的基本和组，就可以$O(\sqrt{n})$地求$f$的前缀和。
求$\frac{f}{g}$在powerful numberes处的值，如果可以快速求$f,g$在素数幂处的值，爆力卷起来复杂度就是$O(\frac{\sqrt{n}}{\log n})$。
求基本和组的话，按$\Theta(n^\frac{2}{3})$根号分治。
如何找这个$g$?通过基本和组狄利克雷乘除的trick，我们可以解决一大类$g$的基本和组。比如考虑$f(p)$是简单多项式的情况，注意到卷$\mathrm{id}_k$就是给$g(p)$加上了$p^k$，除的话就是减去，直接凑即可。
如果性质很不好，比如经典的，给一个常数$c$，筛$f(p)=p\operatorname{xor}c$的前缀和，那还是使用min_25筛。
强硬的筛法。
https://negiizhao.blog.uoj.ac/blog/7165
首先我们考虑如何求一个只有素数处有值且前缀和易于计算的完全积性函数的基本和组。
dgf是各素数dgf的乘积。考虑我们从一个完整的dgf的基本和组开始，每次把一个$\leq\sqrt{n}$的素数的dgf除掉，此时这个素数自己也被除掉了，所以我们还要把它补回来。每个素数是$O(\min(\sqrt{n},\frac{n}{p^2})\log_p n)$的，因为它的dgf只有$\log_p n$项，并且基本和组中$<p^2$的位置是不需要处理的，而$\geq p^2$的$\frac{n}{k}$只有$\min(\sqrt{n},\frac{n}{p^2})$个。对于$p\leq n^\frac{1}{4}$，复杂度是$O(\frac{n^\frac{3}{4}}{\log n})$。对于$p>n^\frac{1}{4}$，积一下，复杂度就只有$\tilde{O}(\sqrt{n})$啦。
类似于倒着做这个过程地，我们可以得到一个积性函数前缀和的方法。
如果我们可以把$\leq\sqrt{n}$的素数都卷起来，剩下的素数dgf就只有一项有贡献，而刚才我们已经说明了怎么算这部分的基本和组。这被称为 洲阁筛。
如果不需要求基本和组，只需要求一个前缀和，直接不记忆化地搜，在我们能见到的范围内这玩意跑的更快。这被称为 min_25筛。
min_25筛的优化
https://blog.csdn.net/whzzt/article/details/104105025
卷还是太慢了，考虑如果我们做一个$\ln-\exp$，就变成加法了，而加一个素数dgf的$\ln$，复杂度直接就是$O(\log_p n)$。
取根号分治阈值$n^\frac{1}{6}$，对于$>n^\frac{1}{6},\leq n^\frac{1}{2}$的素数做$\ln-\exp$，设它们$\ln$的和是$F$，这可以$\tilde{O}(\sqrt{n})$地计算出来，那么$\exp$的时候我们只需要计算$F$的$1,2,3,4,5$次幂，因为$6$次幂就在$n$以内全$0$啦，复杂度$O(n^\frac{2}{3})$。对于$\leq n^\frac{1}{6}$的部分，爆力卷到答案里，复杂度是$O(\frac{n^\frac{2}{3}}{\log n})$，使用同样的方法我们也可以$O(\frac{n^\frac{2}{3}}{\log n})$地求出只考虑素数的基本和组。总复杂度$O(n^\frac{2}{3})$。
考虑怎么给中间那部分砍砍$\log$，注意到$F$只有素数幂处有值，素数幂只有$O(\frac{\sqrt{n}}{\log n})$个，那么它的基本和组中也最多只有$O(\frac{\sqrt{n}}{\log n})$个不同的值。显然基本和组是递增的，还是按$\Theta(n^\frac{2}{3})$根号分治，这以上的部分卷基本和组的时候把相邻相同的值合并起来就除掉了一个$\log$。
以内的部分则需要线筛。显然$F^k$只在每个素因数都超过$n^\frac{1}{6}$的数处有值，注意到根据和轮子筛类似的分析，$\Theta(n^\frac{2}{3})$以内这样的数只有$O(\frac{n^\frac{2}{3}}{\log n})$个，并且显然这些数的乘除是封闭的，我们只在这上面跑一个线筛，复杂度就是$O(\frac{n^\frac{2}{3}}{\log n})$。这被称为 zzt求和法。