杜教筛用来解决类似求$\sum_{i=1}^nf(i)$的问题
设$S(n)=\sum_{i=1}^nf(i)$
假如我们现在找到了一个积性函数$g$，那么考虑下式（其中$*$表示狄利克雷卷积）
对于可逆下三角矩阵$A$（可以归纳证明$A^{-1}$也是下三角矩阵）,有$f=Ag$,那么$g=A^{-1}f$
即:
$$f_i=\sum_{j=0}^ia_{ij}g_j\Rightarrow g_i=\sum_{j=0}^ib_{ij}f_j$$
其中:$$\sum_{k=0}^na_{ik}b_{kj}=[i==j]$$
Min_25筛用来求一个函数的前缀和
如果函数是积性函数就可以做，如果不是积性函数的话有一部分也是可以做的
算法过程就像是在模拟埃氏筛法
时间复杂度是$O(\frac{n^{\frac{3}{4}}}{log(\sqrt{n})})$，然而我并不会证
PhoenixGS
Genius
Yuyao, China
文章
27
分类
0
标签
22
Update your browser to view this website correctly. Update my browser now
×